Abstract#动态规划#状压DP#TSP问题1. 题目题目Luogu P1171 售货员的难题核心思路状态压缩动态规划。定义dp[status][cur]表示当前已经访问过的城市集合为status且当前位于城市cur要访问完所有剩余城市并最终返回城市0的最短路径长度。转移时枚举下一个未访问的城市i则dp[status][cur] min(G[cur][i] dp[status | (1i)][i])。复杂度时间复杂度O ( n 2 × 2 n ) O(n^2 \times 2^n)O(n2×2n)每个状态枚举n个城市空间复杂度O ( n × 2 n ) O(n\times 2^n)O(n×2n)。2. 代码#includeiostream#includevector#includeclimitsusingnamespacestd;constintMAXN25;intn;vectorvectorintG(MAXN,vectorint(MAXN,0));intf(intstatus,intcur,vectorvectorintdp){if(dp[status][cur]!-1)returndp[status][cur];if(status((1n)-1))returnG[cur][0];intansINT_MAX;for(inti0;in;i){if((status(1i))0){ansmin(ans,G[cur][i]f(status|(1i),i,dp));}}dp[status][cur]ans;returnans;}intmain(){cinn;for(inti0;in;i){for(intj0;jn;j){cinG[i][j];}}vectorvectorintdp(1n,vectorint(n,-1));coutf(1,0,dp);return0;}3. 心得边界条件做题时忽略了这一点。当所有城市都已访问status (1 n) - 1时需要返回起点0代价为G[cur][0]。位运算优先级在判断某位是否为0时status (1 i)必须加括号因为的优先级高于。误写为if (status (1 i) 0) 会被解析为status ((1 i) 0)永远为0导致条件永远不成立。这是一点务必牢记。4. 相关题目LeetCode 847. 访问所有节点的最短路径