首页 > 代码库 > 3.4 熟练掌握动态规划——状态压缩DP
3.4 熟练掌握动态规划——状态压缩DP
从旅行商问题说起——
给定一个图，n个节点（n<=15)，求从a节点出发，经历每个节点仅一次，最后回到a，需要的最短时间。
分析：
设定状态S代表当前已经走过的城市的集合，显然，S<=(1<<n)-1.
dp[k][s]——从a走到k，已经经历过的节点集合为s，按照规则走回a所需要的最短时间。
初始化：dp[k][s]=-1
int DP(int K,int S){ if (dp[K][S]!=-1) { return dp[K][S]; } if (K==a && S==(1<<n)-1) { //已经走回了A，并且所有点都走过一次 return dp[K][S]=0; } dp[K][S]=INF; for (int i=0;i<adj[K].size();i++) { //枚举K的下一个点 int v=edges[adj[K][i]].to; int dist=edges[adj[K][i]].dist; if (!(S>>(v-1) & 1))//如果这个点还没有走过 { int val=DP(v,S | (1<<(v-1))); if (val!=INF) { dp[K][S]=min(dp[K][S],val+dist); } } } return dp[K][S];}
3.4 熟练掌握动态规划——状态压缩DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。