{"id":108977,"date":"2026-09-23T04:16:50","date_gmt":"2026-09-22T20:16:50","guid":{"rendered":"https:\/\/www.wsisp.com\/helps\/108977.html"},"modified":"2026-09-23T04:16:50","modified_gmt":"2026-09-22T20:16:50","slug":"%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%e8%bf%9b%e9%98%b6%ef%bc%9a%e7%8a%b6%e6%80%81%e5%8e%8b%e7%bc%a9-dp%ef%bc%88state-compression-dp%ef%bc%89%e4%b8%8e%e6%97%85%e8%a1%8c%e5%95%86%e9%97%ae%e9%a2%98","status":"publish","type":"post","link":"https:\/\/www.wsisp.com\/helps\/108977.html","title":{"rendered":"\u52a8\u6001\u89c4\u5212\u8fdb\u9636\uff1a\u72b6\u6001\u538b\u7f29 DP\uff08State Compression DP\uff09\u4e0e\u65c5\u884c\u5546\u95ee\u9898\uff08TSP\uff09\u4f4d\u8fd0\u7b97\u4f18\u5316"},"content":{"rendered":"<h2>\u52a8\u6001\u89c4\u5212\u8fdb\u9636&#xff1a;\u72b6\u6001\u538b\u7f29 DP&#xff08;State Compression DP&#xff09;\u4e0e\u65c5\u884c\u5546\u95ee\u9898&#xff08;TSP&#xff09;\u4f4d\u8fd0\u7b97\u4f18\u5316<\/h2>\n<p><img decoding=\"async\" src=\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/09\/20260922201648-6ab2e2309509c.webp\" alt=\"\u5c01\u9762\u4fe1\u606f\u56fe\" \/><\/p>\n<p>\u5728\u52a8\u6001\u89c4\u5212&#xff08;Dynamic Programming&#xff09;\u7684\u9ad8\u9636\u9898\u578b\u4e0e\u8fd0\u7b79\u4f18\u5316\u7b97\u6cd5\u4e2d&#xff0c;\u6709\u4e00\u7c7b\u6781\u5176\u7279\u6b8a\u7684 NP-Hard \u7ec4\u5408\u4f18\u5316\u95ee\u9898&#xff1a;<\/p>\n<ul>\n<li>\u65c5\u884c\u5546\u95ee\u9898&#xff08;Traveling Salesperson Problem&#xff0c;TSP&#xff09;&#xff1a;\u904d\u5386 $N$ \u4e2a\u57ce\u5e02\u6bcf\u4e2a\u57ce\u5e02\u6070\u597d\u4e00\u6b21\u5e76\u56de\u5230\u8d77\u70b9\u7684\u6700\u77ed\u603b\u8ddd\u79bb&#xff1b;<\/li>\n<li>LeetCode 847&#xff1a;\u8bbf\u95ee\u6240\u6709\u8282\u70b9\u7684\u6700\u77ed\u8def\u5f84&#xff1b;<\/li>\n<li>\u68cb\u76d8\u6446\u653e\u95ee\u9898&#xff08;\u5982\u7ecf\u5178\u7684\u8499\u5fb7\u91cc\u5b89\u7684\u68a6\u60f3 \/ \u4e92\u4e0d\u653b\u51fb\u7684\u56fd\u738b\u4e0e\u70ae\u8f66&#xff09;\u3002<\/li>\n<\/ul>\n<p>\u5728\u8fd9\u4e9b\u95ee\u9898\u4e2d&#xff0c;\u6570\u636e\u89c4\u6a21\u901a\u5e38\u6781\u5c0f&#xff08;\u5982 $N \\\\le 16 \\\\sim 20$&#xff09;&#xff0c;\u4f46\u6bcf\u4e2a\u5143\u7d20\u62e5\u6709\u201c\u88ab\u9009\u4e2d\/\u672a\u88ab\u9009\u4e2d\u201d\u3001\u201c\u88ab\u8bbf\u95ee\/\u672a\u88ab\u8bbf\u95ee\u201d\u7b49\u79bb\u6563\u4e8c\u5143\u72b6\u6001\u3002\u5982\u679c\u7528\u666e\u901a\u7684\u6570\u7ec4\u6765\u8bb0\u5f55\u201c\u5f53\u524d\u54ea\u4e9b\u57ce\u5e02\u5df2\u7ecf\u88ab\u8bbf\u95ee\u8fc7\u4e86\u201d&#xff0c;\u72b6\u6001\u7ef4\u5ea6\u5c06\u8fbe\u5230\u591a\u7ef4\u6570\u7ec4\u65e0\u6cd5\u627f\u53d7\u7684\u590d\u6742\u5ea6\u3002<\/p>\n<p>\u72b6\u6001\u538b\u7f29\u52a8\u6001\u89c4\u5212&#xff08;State Compression DP&#xff0c;\u7b80\u79f0\u72b6\u538b DP&#xff09; \u51ed\u501f\u8ba1\u7b97\u673a\u5e95\u5c42\u7684\u4e8c\u8fdb\u5236\u4f4d\u8fd0\u7b97&#xff08;Bitmasking&#xff09;&#xff1a;\u5c06\u4e00\u4e2a\u5927\u5c0f\u4e3a $N$ \u7684\u5e03\u5c14\u72b6\u6001\u96c6\u5408&#xff0c;\u7cbe\u786e\u538b\u7f29\u8fdb\u4e00\u4e2a 32 \u4f4d\u6574\u578b\u6574\u6570 int state \u7684\u5404\u4e2a\u4e8c\u8fdb\u5236\u4f4d\u4e2d&#xff01;\u901a\u8fc7\u6781\u81f4\u7684\u4f4d\u79fb\u4e0e\u4f4d\u8fd0\u7b97&#xff0c;\u5c06\u539f\u672c\u6307\u6570\u7ea7\u66b4\u641c\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u5927\u5e45\u4f18\u5316&#xff0c;\u5728\u6beb\u79d2\u7ea7\u65f6\u95f4\u5185\u5f81\u670d\u539f\u672c\u4e0d\u53ef\u89e3\u7684\u7ec4\u5408\u96be\u9898\u3002<\/p>\n<p>\u4eca\u5929\u6211\u4eec\u628a\u72b6\u538b DP \u7684\u4e8c\u8fdb\u5236\u4f4d\u8fd0\u7b97\u5fc3\u6cd5\u3001\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u63a8\u5bfc\u4e0e TSP \u7ecf\u5178\u6a21\u677f\u5f7b\u5e95\u8bb2\u900f\u3002<\/p>\n<hr \/>\n<h4>\u4e00\u3001\u72b6\u6001\u538b\u7f29\u6838\u5fc3\u4f4d\u8fd0\u7b97\u64cd\u4f5c\u5b57\u5178<\/h4>\n<p>\u8bbe\u72b6\u6001\u96c6\u5408\u7528\u6574\u578b\u53d8\u91cf mask \u8868\u793a&#xff08;\u7b2c $i$ \u4f4d\u4e3a 1 \u4ee3\u8868\u7b2c $i$ \u4e2a\u57ce\u5e02\u5df2\u88ab\u8bbf\u95ee&#xff0c;\u4e3a 0 \u4ee3\u8868\u672a\u8bbf\u95ee&#xff09;&#xff1a;<\/p>\n<p>graph TD<br \/>\n    subgraph \u4e8c\u8fdb\u5236\u4f4d\u8fd0\u7b97\u6838\u5fc3\u64cd\u4f5c (0-indexed)<br \/>\n        Op1[&#034;1. \u68c0\u67e5\u7b2c i \u4e2a\u5143\u7d20\u662f\u5426\u5df2\u88ab\u8bbf\u95ee: (mask &gt;&gt; i) &amp; 1 &#061;&#061; 1&#034;]<br \/>\n        Op2[&#034;2. \u5c06\u7b2c i \u4e2a\u5143\u7d20\u6807\u8bb0\u4e3a\u5df2\u8bbf\u95ee: mask | (1 &lt;&lt; i)&#034;]<br \/>\n        Op3[&#034;3. \u5c06\u7b2c i \u4e2a\u5143\u7d20\u4ece\u96c6\u5408\u4e2d\u79fb\u9664: mask &amp; ~(1 &lt;&lt; i)&#034;]<br \/>\n        Op4[&#034;4. \u5c06\u7b2c i \u4e2a\u5143\u7d20\u7684\u72b6\u6001\u53d6\u53cd: mask ^ (1 &lt;&lt; i)&#034;]<br \/>\n        Op5[&#034;5. \u904d\u5386\u5168\u96c6\u72b6\u6001\u7a7a\u95f4: for mask &#061; 0 to (1 &lt;&lt; N) &#8211; 1&#034;]<br \/>\n    end<\/p>\n<table>\n<tr>\u4e1a\u52a1\u903b\u8f91\u4e8c\u8fdb\u5236\u4f4d\u8fd0\u7b97\u8868\u8fbe\u5f0f\u7269\u7406\u8bf4\u660e<\/tr>\n<tbody>\n<tr>\n<td>\u5224\u65ad\u7b2c $i$ \u4f4d\u662f\u5426\u4e3a 1<\/td>\n<td>(mask &amp; (1 &lt;&lt; i)) !&#061; 0 \u6216 ((mask &gt;&gt; i) &amp; 1) &#061;&#061; 1<\/td>\n<td>\u68c0\u67e5\u7b2c $i$ \u4e2a\u5143\u7d20\u662f\u5426\u5b58\u5728\u4e8e\u5f53\u524d\u96c6\u5408\u4e2d<\/td>\n<\/tr>\n<tr>\n<td>\u5c06\u7b2c $i$ \u4f4d\u8bbe\u4e3a 1<\/td>\n<td>&#096;mask<\/td>\n<td>(1 &lt;&lt; i)&#096;<\/td>\n<\/tr>\n<tr>\n<td>\u5c06\u7b2c $i$ \u4f4d\u6e05\u96f6&#xff08;\u8bbe\u4e3a 0&#xff09;<\/td>\n<td>mask &amp; ~(1 &lt;&lt; i)<\/td>\n<td>\u4ece\u96c6\u5408\u4e2d\u5220\u9664\u7b2c $i$ \u4e2a\u5143\u7d20<\/td>\n<\/tr>\n<tr>\n<td>\u5c06\u7b2c $i$ \u4f4d\u7ffb\u8f6c<\/td>\n<td>mask ^ (1 &lt;&lt; i)<\/td>\n<td>\u72b6\u6001\u53d6\u53cd<\/td>\n<\/tr>\n<tr>\n<td>\u83b7\u53d6\u96c6\u5408\u4e2d\u5143\u7d20\u7684\u603b\u4e2a\u6570<\/td>\n<td>Integer.bitCount(mask)<\/td>\n<td>\u7edf\u8ba1\u4e8c\u8fdb\u5236\u4e2d 1 \u7684\u4e2a\u6570&#xff08;\u5373\u5df2\u8bbf\u95ee\u57ce\u5e02\u6570&#xff09;<\/td>\n<\/tr>\n<tr>\n<td>\u63d0\u53d6\u6700\u4f4e\u4f4d\u7684 1&#xff08;Lowbit&#xff09;<\/td>\n<td>mask &amp; (-mask)<\/td>\n<td>\u5feb\u901f\u679a\u4e3e\u96c6\u5408\u4e2d\u7684\u5143\u7d20<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<hr \/>\n<h4>\u4e8c\u3001\u65c5\u884c\u5546\u95ee\u9898&#xff08;TSP&#xff09;\u72b6\u538b DP \u72b6\u6001\u5b9a\u4e49\u4e0e\u8f6c\u79fb\u65b9\u7a0b<\/h4>\n<p>\u7ed9\u5b9a $N$ \u4e2a\u57ce\u5e02\u4ee5\u53ca\u4efb\u610f\u4e24\u4e2a\u57ce\u5e02 $i$ \u4e0e $j$ \u4e4b\u95f4\u7684\u8ddd\u79bb\u77e9\u9635 dist[i][j]\u3002\u6c42\u89e3\u4ece\u8d77\u70b9 0 \u51fa\u53d1&#xff0c;\u8bbf\u95ee\u5b8c\u6240\u6709\u57ce\u5e02\u6070\u597d\u4e00\u6b21\u7684\u6700\u77ed\u8def\u5f84\u603b\u957f\u5ea6\u3002<\/p>\n<h5>1. \u72b6\u6001\u5b9a\u4e49&#xff1a;<\/h5>\n<p>$$\\\\mathbf{dp[\\\\text{mask}][u]}$$<\/p>\n<ul>\n<li>\u7269\u7406\u542b\u4e49&#xff1a;\u5f53\u524d\u5df2\u7ecf\u8bbf\u95ee\u8fc7\u7684\u57ce\u5e02\u96c6\u5408\u4e3a mask&#xff08;\u4e8c\u8fdb\u5236\u7f16\u7801&#xff09;&#xff0c;\u4e14\u5f53\u524d\u505c\u7559\u5728\u57ce\u5e02 $u$ \u65f6\u7684\u3010\u6700\u5c0f\u7d2f\u8ba1\u8def\u5f84\u5f00\u9500\u3011&#xff01;<\/li>\n<\/ul>\n<h5>2. \u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b&#xff08;\u81ea\u5e95\u5411\u4e0a\u5411\u5916\u9012\u63a8&#xff09;&#xff1a;<\/h5>\n<p>\u5f53\u524d\u72b6\u6001\u4e3a $(\\\\text{mask}, u)$&#xff0c;\u6211\u4eec\u5c1d\u8bd5\u4ece\u57ce\u5e02 $u$ \u8d70\u5411\u4e0b\u4e00\u4e2a\u5c1a\u672a\u8bbf\u95ee\u8fc7\u7684\u57ce\u5e02 $v$&#xff08;\u5373\u6ee1\u8db3 (mask &amp; (1 &lt;&lt; v)) &#061;&#061; 0&#xff09;&#xff1a;<\/p>\n<p>$$\\\\mathbf{dp[\\\\text{mask} \\\\mid (1 \\\\ll v)][v] &#061; \\\\min \\\\left( dp[\\\\text{mask} \\\\mid (1 \\\\ll v)][v], \\\\ dp[\\\\text{mask}][u] &#043; \\\\text{dist}[u][v] \\\\right)}$$<\/p>\n<p>graph LR<br \/>\n    S1[&#034;dp[mask][u]: \u5df2\u7ecf\u8bbf\u95ee\u96c6\u5408 mask, \u505c\u7559\u5728\u57ce\u5e02 u&#034;] &#8211;&gt;|\u8d70\u5411\u672a\u8bbf\u95ee\u57ce\u5e02 v| S2[&#034;dp[mask | (1 &lt;&lt; v)][v]: \u8bbf\u95ee\u96c6\u5408\u6269\u5145, \u505c\u7559\u5728\u57ce\u5e02 v&#034;]<br \/>\n    Note[&#034;\u8f6c\u79fb\u5f00\u9500: &#043; dist[u][v]&#034;]<\/p>\n<h5>3. \u521d\u59cb\u72b6\u6001\u4e0e\u6700\u7ec8\u7b54\u6848&#xff1a;<\/h5>\n<ul>\n<li>\u521d\u59cb\u5316&#xff1a;\u6240\u6709 $dp$ \u6570\u7ec4\u8bbe\u4e3a\u6b63\u65e0\u7a77&#xff08;INF&#xff09;&#xff1b;<\/li>\n<li>\u8d77\u70b9&#xff1a;$dp[1 \\\\ll 0][0] &#061; dp[1][0] &#061; 0$&#xff08;\u96c6\u5408\u4e2d\u4ec5\u5305\u542b\u8d77\u70b9 0&#xff0c;\u505c\u7559\u5728\u57ce\u5e02 0&#xff0c;\u8017\u65f6\u4e3a 0&#xff09;&#xff1b;<\/li>\n<li>\u6700\u7ec8\u76ee\u6807&#xff1a;$dp[(1 \\\\ll N) &#8211; 1][\\\\text{last_city}]$&#xff08;\u6240\u6709\u4e8c\u8fdb\u5236\u4f4d\u5168\u90e8\u4e3a 1&#xff0c;\u4ee3\u8868\u5168\u96c6\u8986\u76d6&#xff09;\u3002<\/li>\n<\/ul>\n<hr \/>\n<h4>\u5de5\u4e1a\u7ea7 TSP \u72b6\u538b DP Java \u5b9e\u73b0\u6a21\u677f<\/h4>\n<p>import java.util.Arrays;<\/p>\n<p>public class TspStateCompressionDp {<\/p>\n<p>    private static final int INF &#061; 0x3f3f3f3f;<\/p>\n<p>    public int solveTsp(int n, int[][] dist) {<br \/>\n        int totalStates &#061; 1 &lt;&lt; n; \/\/ 2^N \u79cd\u72b6\u6001\u96c6\u5408<br \/>\n        int[][] dp &#061; new int[totalStates][n];<\/p>\n<p>        \/\/ 1. \u521d\u59cb\u5316 dp \u6570\u7ec4\u4e3a\u65e0\u7a77\u5927<br \/>\n        for (int i &#061; 0; i &lt; totalStates; i&#043;&#043;) {<br \/>\n            Arrays.fill(dp[i], INF);<br \/>\n        }<\/p>\n<p>        \/\/ 2. \u8d77\u70b9\u521d\u59cb\u72b6\u6001&#xff1a;\u4ece\u57ce\u5e02 0 \u51fa\u53d1<br \/>\n        dp[1][0] &#061; 0; \/\/ 1 \u7684\u4e8c\u8fdb\u5236\u4e3a 00&#8230;001 (\u4ec5\u8bbf\u95ee\u4e86\u57ce\u5e02 0)<\/p>\n<p>        \/\/ 3. \u72b6\u6001\u4ece\u5c0f\u5230\u5927\u9012\u63a8\u904d\u5386 (\u4fdd\u8bc1\u5b50\u72b6\u6001\u4e00\u5b9a\u5148\u4e8e\u7236\u72b6\u6001\u8ba1\u7b97\u5b8c\u6210!)<br \/>\n        for (int mask &#061; 1; mask &lt; totalStates; mask&#043;&#043;) {<br \/>\n            for (int u &#061; 0; u &lt; n; u&#043;&#043;) {<br \/>\n                \/\/ \u82e5\u5f53\u524d\u96c6\u5408 mask \u4e2d\u6839\u672c\u4e0d\u5305\u542b\u57ce\u5e02 u&#xff0c;\u5219\u8be5\u72b6\u6001\u4e0d\u53ef\u80fd\u5b58\u5728&#xff0c;\u76f4\u63a5\u8df3\u8fc7<br \/>\n                if ((mask &amp; (1 &lt;&lt; u)) &#061;&#061; 0 || dp[mask][u] &#061;&#061; INF) {<br \/>\n                    continue;<br \/>\n                }<\/p>\n<p>                \/\/ \u5c1d\u8bd5\u4ece\u5f53\u524d\u57ce\u5e02 u \u8d70\u5411\u4e0b\u4e00\u4e2a\u672a\u8bbf\u95ee\u57ce\u5e02 v<br \/>\n                for (int v &#061; 0; v &lt; n; v&#043;&#043;) {<br \/>\n                    \/\/ \u82e5\u57ce\u5e02 v \u5c1a\u672a\u88ab\u8bbf\u95ee<br \/>\n                    if ((mask &amp; (1 &lt;&lt; v)) &#061;&#061; 0) {<br \/>\n                        int nextMask &#061; mask | (1 &lt;&lt; v);<br \/>\n                        dp[nextMask][v] &#061; Math.min(dp[nextMask][v], dp[mask][u] &#043; dist[u][v]);<br \/>\n                    }<br \/>\n                }<br \/>\n            }<br \/>\n        }<\/p>\n<p>        \/\/ 4. \u7edf\u8ba1\u8bbf\u95ee\u5b8c\u5168\u90e8\u57ce\u5e02&#xff08;mask &#061; (1 &lt;&lt; n) &#8211; 1&#xff09;\u5e76\u8fd4\u56de\u8d77\u70b9 0 \u7684\u6700\u77ed\u56de\u8def<br \/>\n        int allVisitedMask &#061; (1 &lt;&lt; n) &#8211; 1;<br \/>\n        int minTotalCost &#061; INF;<br \/>\n        for (int u &#061; 0; u &lt; n; u&#043;&#043;) {<br \/>\n            if (dp[allVisitedMask][u] !&#061; INF) {<br \/>\n                \/\/ \u52a0\u4e0a\u4ece\u6700\u540e\u505c\u7559\u7684\u57ce\u5e02 u \u56de\u5230\u8d77\u70b9 0 \u7684\u8ddd\u79bb<br \/>\n                minTotalCost &#061; Math.min(minTotalCost, dp[allVisitedMask][u] &#043; dist[u][0]);<br \/>\n            }<br \/>\n        }<\/p>\n<p>        return minTotalCost;<br \/>\n    }<br \/>\n}<\/p>\n<hr \/>\n<h4>\u590d\u6742\u5ea6\u5bf9\u6bd4\u4e0e\u65f6\u7a7a\u5206\u6790<\/h4>\n<table>\n<tr>\u7b97\u6cd5\u65b9\u6848\u65f6\u95f4\u590d\u6742\u5ea6\u7a7a\u95f4\u590d\u6742\u5ea6$N &#061; 16$ \u65f6\u7684\u8ba1\u7b97\u91cf\u7ea7<\/tr>\n<tbody>\n<tr>\n<td>\u6734\u7d20\u5168\u6392\u5217\u66b4\u529b\u641c\u7d22&#xff08;DFS \/ Brute-Force&#xff09;<\/td>\n<td>$\\\\mathcal{O}(N!)$<\/td>\n<td>$\\\\mathcal{O}(N)$<\/td>\n<td>$16! \\\\approx 2.09 \\\\times 10^{13}$&#xff08;\u76f4\u63a5\u8d85\u65f6\u66b4\u6bd9&#xff01;&#xff09;<\/td>\n<\/tr>\n<tr>\n<td>\u72b6\u538b\u52a8\u6001\u89c4\u5212&#xff08;Held-Karp \u7b97\u6cd5&#xff09;<\/td>\n<td>$\\\\mathcal{O}(2^N \\\\cdot N^2)$<\/td>\n<td>$\\\\mathcal{O}(2^N \\\\cdot N)$<\/td>\n<td>$2^{16} \\\\times 16^2 \\\\approx 1.67 \\\\times 10^7$&#xff08;\u6beb\u79d2\u7ea7\u79d2\u6740&#xff01;&#xff09;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<hr \/>\n<h4>\u5b9e\u4e60\u751f\u7684\u7b97\u6cd5\u8fdb\u9636\u603b\u7ed3<\/h4>\n<p>\u72b6\u538b DP \u662f\u4f4d\u8fd0\u7b97&#xff08;Bitwise Manipulation&#xff09;\u4e0e\u52a8\u6001\u89c4\u5212&#xff08;DP&#xff09;\u6700\u7cbe\u5999\u7684\u7ed3\u5408\u4f53&#xff1a;\u5b83\u5229\u7528\u4e8c\u8fdb\u5236\u5e95\u5c42\u7684\u4f4d\u8868\u793a&#xff0c;\u5c06\u539f\u672c\u79bb\u6563\u9ad8\u7ef4\u7684\u96c6\u5408\u72b6\u6001\u4f18\u96c5\u538b\u7f29\u8fdb\u5355\u4e2a\u6574\u578b\u5bc4\u5b58\u5668\u4e2d&#xff0c;\u5728\u4fdd\u8bc1\u72b6\u6001\u65e0\u540e\u6548\u6027\u7684\u540c\u65f6&#xff0c;\u5c06\u9636\u4e58\u7ea7\u7684\u66b4\u641c\u5f00\u9500\u538b\u7f29\u4e3a\u6307\u6570\u7ea7\u591a\u9879\u5f0f\u3002\u7262\u8bb0 \u201c\u5224\u65ad\u5305\u542b\u7528 &amp;\u3001\u52a0\u5165\u96c6\u5408\u7528 |\u3001\u904d\u5386\u72b6\u6001\u4ece\u5c0f\u5230\u5927\u4fdd\u8bc1\u62d3\u6251\u6709\u5e8f\u201d \u4e09\u5927\u5fc3\u6cd5&#xff0c;\u9762\u5bf9\u5404\u7c7b\u7f51\u683c\u8986\u76d6\u4e0e\u65c5\u884c\u5546\u96be\u9898&#xff0c;\u4f60\u90fd\u80fd\u5199\u51fa\u95ea\u7535\u822c\u8fc5\u6377\u7684\u72b6\u538b\u89e3\u6cd5\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u52a8\u6001\u89c4\u5212\u8fdb\u9636&#xff1a;\u72b6\u6001\u538b\u7f29 DP&#xff08;State Compression DP&#xff09;\u4e0e\u65c5\u884c\u5546\u95ee\u9898&#xff08;TSP&#xff09;\u4f4d\u8fd0\u7b97\u4f18\u5316\u5728\u52a8\u6001\u89c4\u5212&#xff08;Dynamic Programming&#xff09;\u7684\u9ad8\u9636\u9898\u578b\u4e0e\u8fd0\u7b79\u4f18\u5316\u7b97\u6cd5\u4e2d&#xff0c;\u6709\u4e00\u7c7b\u6781\u5176\u7279\u6b8a\u7684 NP-Hard \u7ec4\u5408\u4f18\u5316\u95ee\u9898&#xff1a;<br \/>\n\u65c5\u884c\u5546\u95ee\u9898&#xff08;Traveling Salesperson Problem&#xff0c;TSP&amp;#xff09<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[66,2692,50,4323,427],"topic":[],"class_list":["post-108977","post","type-post","status-publish","format-standard","hentry","category-server","tag-ai","tag-leetcode","tag-50","tag-4323","tag-427"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v20.3 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>\u52a8\u6001\u89c4\u5212\u8fdb\u9636\uff1a\u72b6\u6001\u538b\u7f29 DP\uff08State Compression DP\uff09\u4e0e\u65c5\u884c\u5546\u95ee\u9898\uff08TSP\uff09\u4f4d\u8fd0\u7b97\u4f18\u5316 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.wsisp.com\/helps\/108977.html\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u52a8\u6001\u89c4\u5212\u8fdb\u9636\uff1a\u72b6\u6001\u538b\u7f29 DP\uff08State Compression DP\uff09\u4e0e\u65c5\u884c\u5546\u95ee\u9898\uff08TSP\uff09\u4f4d\u8fd0\u7b97\u4f18\u5316 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"og:description\" content=\"\u52a8\u6001\u89c4\u5212\u8fdb\u9636&#xff1a;\u72b6\u6001\u538b\u7f29 DP&#xff08;State Compression DP&#xff09;\u4e0e\u65c5\u884c\u5546\u95ee\u9898&#xff08;TSP&#xff09;\u4f4d\u8fd0\u7b97\u4f18\u5316\u5728\u52a8\u6001\u89c4\u5212&#xff08;Dynamic Programming&#xff09;\u7684\u9ad8\u9636\u9898\u578b\u4e0e\u8fd0\u7b79\u4f18\u5316\u7b97\u6cd5\u4e2d&#xff0c;\u6709\u4e00\u7c7b\u6781\u5176\u7279\u6b8a\u7684 NP-Hard \u7ec4\u5408\u4f18\u5316\u95ee\u9898&#xff1a; \u65c5\u884c\u5546\u95ee\u9898&#xff08;Traveling Salesperson Problem&#xff0c;TSP&amp;#xff09\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.wsisp.com\/helps\/108977.html\" \/>\n<meta property=\"og:site_name\" content=\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"article:published_time\" content=\"2026-09-22T20:16:50+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/09\/20260922201648-6ab2e2309509c.webp\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/108977.html\",\"url\":\"https:\/\/www.wsisp.com\/helps\/108977.html\",\"name\":\"\u52a8\u6001\u89c4\u5212\u8fdb\u9636\uff1a\u72b6\u6001\u538b\u7f29 DP\uff08State Compression DP\uff09\u4e0e\u65c5\u884c\u5546\u95ee\u9898\uff08TSP\uff09\u4f4d\u8fd0\u7b97\u4f18\u5316 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"isPartOf\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\"},\"datePublished\":\"2026-09-22T20:16:50+00:00\",\"dateModified\":\"2026-09-22T20:16:50+00:00\",\"author\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/108977.html#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.wsisp.com\/helps\/108977.html\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/108977.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/www.wsisp.com\/helps\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u52a8\u6001\u89c4\u5212\u8fdb\u9636\uff1a\u72b6\u6001\u538b\u7f29 DP\uff08State Compression DP\uff09\u4e0e\u65c5\u884c\u5546\u95ee\u9898\uff08TSP\uff09\u4f4d\u8fd0\u7b97\u4f18\u5316\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\",\"url\":\"https:\/\/www.wsisp.com\/helps\/\",\"name\":\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"description\":\"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"contentUrl\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"caption\":\"admin\"},\"sameAs\":[\"http:\/\/wp.wsisp.com\"],\"url\":\"https:\/\/www.wsisp.com\/helps\/author\/admin\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u52a8\u6001\u89c4\u5212\u8fdb\u9636\uff1a\u72b6\u6001\u538b\u7f29 DP\uff08State Compression DP\uff09\u4e0e\u65c5\u884c\u5546\u95ee\u9898\uff08TSP\uff09\u4f4d\u8fd0\u7b97\u4f18\u5316 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.wsisp.com\/helps\/108977.html","og_locale":"zh_CN","og_type":"article","og_title":"\u52a8\u6001\u89c4\u5212\u8fdb\u9636\uff1a\u72b6\u6001\u538b\u7f29 DP\uff08State Compression DP\uff09\u4e0e\u65c5\u884c\u5546\u95ee\u9898\uff08TSP\uff09\u4f4d\u8fd0\u7b97\u4f18\u5316 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","og_description":"\u52a8\u6001\u89c4\u5212\u8fdb\u9636&#xff1a;\u72b6\u6001\u538b\u7f29 DP&#xff08;State Compression DP&#xff09;\u4e0e\u65c5\u884c\u5546\u95ee\u9898&#xff08;TSP&#xff09;\u4f4d\u8fd0\u7b97\u4f18\u5316\u5728\u52a8\u6001\u89c4\u5212&#xff08;Dynamic Programming&#xff09;\u7684\u9ad8\u9636\u9898\u578b\u4e0e\u8fd0\u7b79\u4f18\u5316\u7b97\u6cd5\u4e2d&#xff0c;\u6709\u4e00\u7c7b\u6781\u5176\u7279\u6b8a\u7684 NP-Hard \u7ec4\u5408\u4f18\u5316\u95ee\u9898&#xff1a; \u65c5\u884c\u5546\u95ee\u9898&#xff08;Traveling Salesperson Problem&#xff0c;TSP&amp;#xff09","og_url":"https:\/\/www.wsisp.com\/helps\/108977.html","og_site_name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","article_published_time":"2026-09-22T20:16:50+00:00","og_image":[{"url":"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/09\/20260922201648-6ab2e2309509c.webp"}],"author":"admin","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"admin","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"3 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.wsisp.com\/helps\/108977.html","url":"https:\/\/www.wsisp.com\/helps\/108977.html","name":"\u52a8\u6001\u89c4\u5212\u8fdb\u9636\uff1a\u72b6\u6001\u538b\u7f29 DP\uff08State Compression DP\uff09\u4e0e\u65c5\u884c\u5546\u95ee\u9898\uff08TSP\uff09\u4f4d\u8fd0\u7b97\u4f18\u5316 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","isPartOf":{"@id":"https:\/\/www.wsisp.com\/helps\/#website"},"datePublished":"2026-09-22T20:16:50+00:00","dateModified":"2026-09-22T20:16:50+00:00","author":{"@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41"},"breadcrumb":{"@id":"https:\/\/www.wsisp.com\/helps\/108977.html#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.wsisp.com\/helps\/108977.html"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.wsisp.com\/helps\/108977.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/www.wsisp.com\/helps"},{"@type":"ListItem","position":2,"name":"\u52a8\u6001\u89c4\u5212\u8fdb\u9636\uff1a\u72b6\u6001\u538b\u7f29 DP\uff08State Compression DP\uff09\u4e0e\u65c5\u884c\u5546\u95ee\u9898\uff08TSP\uff09\u4f4d\u8fd0\u7b97\u4f18\u5316"}]},{"@type":"WebSite","@id":"https:\/\/www.wsisp.com\/helps\/#website","url":"https:\/\/www.wsisp.com\/helps\/","name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","description":"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41","name":"admin","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/","url":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","contentUrl":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","caption":"admin"},"sameAs":["http:\/\/wp.wsisp.com"],"url":"https:\/\/www.wsisp.com\/helps\/author\/admin"}]}},"_links":{"self":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/108977","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/comments?post=108977"}],"version-history":[{"count":0,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/108977\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media?parent=108977"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/categories?post=108977"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/tags?post=108977"},{"taxonomy":"topic","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/topic?post=108977"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}