{"id":1746,"date":"2025-02-27T16:13:24","date_gmt":"2025-02-27T08:13:24","guid":{"rendered":"http:\/\/114.55.108.251\/?p=1746"},"modified":"2025-03-03T21:56:51","modified_gmt":"2025-03-03T13:56:51","slug":"%e5%8a%9b%e6%89%a3%e9%a2%98%e8%ae%b0%e4%b9%8b%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92","status":"publish","type":"post","link":"https:\/\/guapicoding.com\/?p=1746","title":{"rendered":"\u529b\u6263\u9898\u8bb0\u4e4b\u52a8\u6001\u89c4\u5212"},"content":{"rendered":"\n<p class=\"has-text-align-center\"><em><strong>More content<\/strong><\/em><strong><em>\uff1a<\/em><\/strong><a href=\"https:\/\/guapicoding.com\/?p=1744\" data-type=\"post\" data-id=\"1744\">LeetCode hot100@\u52a8\u6001\u89c4\u5212&amp;\u591a\u7ef4\u52a8\u6001\u89c4\u5212<\/a><\/p>\n\n\n\n<p><em><strong>DP\u662f\u7531\u524d\u4e00\u4e2a\u72b6\u6001\u63a8\u5bfc\u800c\u51fa\uff0c\u800c\u8d2a\u5fc3\u662f\u5728\u5c40\u90e8\u76f4\u63a5\u9009\u62e9\u6700\u4f18 <\/strong><\/em><\/p>\n\n\n\n<p><strong>DP\u4e94\u90e8\u66f2\uff1a<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u786e\u5b9a<strong><em>dp\u6570\u7ec4<\/em><\/strong>\u4ee5\u53ca<strong><em>\u4e0b\u6807<\/em><\/strong>\u7684\u542b\u4e49<\/li>\n\n\n\n<li>\u786e\u5b9a<strong><em>\u9012\u63a8\u516c\u5f0f<\/em><\/strong>(\u72b6\u6001\u8f6c\u79fb\u516c\u5f0f)<\/li>\n\n\n\n<li>dp\u6570\u7ec4\u5982\u4f55<strong><em>\u521d\u59cb\u5316<\/em><\/strong><\/li>\n\n\n\n<li>\u786e\u5b9a<em><strong>\u904d\u5386\u987a\u5e8f<\/strong><\/em><\/li>\n\n\n\n<li>\u4e3e\u4f8b\u63a8\u5bfcdp\u6570\u7ec4<\/li>\n<\/ol>\n\n\n\n<p><strong><em>01\u80cc\u5305\u6a21\u677f\uff1a<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>for(int i = 0; i &lt; weight.size(); i++) { \/\/\u904d\u5386\u7269\u54c1\n    for(int j = bagWeight; j &gt;= weight&#91;i]; j--) { \/\/\u904d\u5386\u80cc\u5305\u5bb9\u91cf(\u4e3a\u4e86\u786e\u4fdd\u6bcf\u4e2a\u7269\u54c1\u6700\u591a\u88ab\u6dfb\u52a0\u4e00\u6b21\uff0c\u6240\u4ee5\u8981\u4ece\u5927\u5230\u5c0f\u53bb\u904d\u5386)        \n        dp&#91;j] = max(dp&#91;j], dp&#91;j - weight&#91;i]] + value&#91;i]); \/\/\u6c42\u80cc\u5305\u5bb9\u7eb3\u7684\u6700\u5927\u4ef7\u503c(\u6dfb\u52a0,\u4e0d\u6dfb\u52a0)\n        dp&#91;j] += dp&#91;j - nums&#91;i]]; \/\/\u6c42\u88c5\u6ee1\u80cc\u5305\u7684\u4e0d\u540c\u7ec4\u5408\u6570\n        \/\/cout &lt;&lt; \"i = \" &lt;&lt; i &lt;&lt; \", j = \" &lt;&lt; j &lt;&lt; \", dp&#91;\" &lt;&lt; j &lt;&lt; \"] = \" &lt;&lt; dp&#91;j] &lt;&lt; endl;\n    }\n}<\/code><\/pre>\n\n\n\n<p><strong><em>\u5b8c\u5168\u80cc\u5305\u6a21\u677f\uff1a<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/\u5e38\u89c4\u6a21\u677f\nfor(int i = 0; i &lt; weight.size(); i++) { \/\/\u904d\u5386\u7269\u54c1\n    for(int j = weight&#91;i]; j &lt;= bagWeight; j++) { \/\/\u904d\u5386\u80cc\u5305\u5bb9\u91cf(\u6bcf\u4e2a\u7269\u54c1\u90fd\u53ef\u4ee5\u591a\u6b21\u6dfb\u52a0\uff0c\u56e0\u6b64\u4ece\u5c0f\u5230\u5927\u53bb\u904d\u5386)\n        dp&#91;j] = max(dp&#91;j], dp&#91;j - weight&#91;i]] + value&#91;i]); \/\/\u6dfb\u52a0or\u4e0d\u6dfb\u52a0\n        \/\/cout &lt;&lt; \"i = \" &lt;&lt; i &lt;&lt; \", j = \" &lt;&lt; j &lt;&lt; \", dp&#91;\" &lt;&lt; j &lt;&lt; \"] = \" &lt;&lt; dp&#91;j] &lt;&lt; endl;\n    }\n}\n\/\/\u6c42\u7ec4\u5408\u79cd\u6570\nfor(int i = 0; i &lt; nums.size(); i++) { \/\/\u904d\u5386\u7269\u54c1\n    for(int j = nums&#91;i]; j &lt;= bagWeight; j++) { \/\/\u904d\u5386\u80cc\u5305\u5bb9\u91cf\n        dp&#91;j] += dp&#91;j - nums&#91;i]]; \/\/\u6c42\u88c5\u6ee1\u80cc\u5305\u7684\u4e0d\u540c\u7ec4\u5408\u6570\n    }\n}\n\/\/\u6c42\u6392\u5217\u79cd\u6570    \nfor(int i = 0; i &lt;= bagWeight; i++) { \/\/\u5148\u904d\u5386\u80cc\u5305\u5bb9\u91cf\n    for(int j = 0; j &lt; nums.size(); j++) { \/\/\u518d\u904d\u5386\u7269\u54c1\n        if(i - nums&#91;j] &gt;= 0) dp&#91;i] += dp&#91;i - nums&#91;j]]; \/\/\u6c42\u88c5\u6ee1\u80cc\u5305\u7684\u4e0d\u540c\u6392\u5217\u6570\n    }\n}<\/code><\/pre>\n\n\n\n<p>ps\uff1aDP\u7684\u4e00\u4e9b\u9898\u76ee\u4e5f\u80fd\u7528\u9012\u5f52\u56de\u6eaf\u641c\u7d22\uff0c\u4f46\u5f80\u5f80\u4f1a\u8d85\u65f6\uff0c\u6bd5\u7adf\u7c7b\u4f3c\u4e8e\u66b4\u529b<\/p>\n\n\n\n<h1 class=\"wp-block-heading\">\u5237\u9898\u5927\u7eb2<\/h1>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>\u57fa\u7840\u9898\u76ee<\/strong>\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/leetcode.cn\/problems\/unique-paths\/\">62. \u4e0d\u540c\u8def\u5f84<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/unique-paths-ii\/\">63. \u4e0d\u540c\u8def\u5f84 II<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/climbing-stairs\/\">70. \u722c\u697c\u68af<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/unique-binary-search-trees\/\">96. \u4e0d\u540c\u7684\u4e8c\u53c9\u641c\u7d22\u6811<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/integer-break\/\">343. \u6574\u6570\u62c6\u5206<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/fibonacci-number\/\">509. \u6590\u6ce2\u90a3\u5951\u6570<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/min-cost-climbing-stairs\/\">746. \u4f7f\u7528\u6700\u5c0f\u82b1\u8d39\u722c\u697c\u68af<\/a><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u80cc\u5305\u95ee\u9898<\/strong>\n<ul class=\"wp-block-list\">\n<li>01\u80cc\u5305\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/leetcode.cn\/problems\/partition-equal-subset-sum\/\">416. \u5206\u5272\u7b49\u548c\u5b50\u96c6<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/ones-and-zeroes\/\">474. \u4e00\u548c\u96f6<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/target-sum\/\">494. \u76ee\u6807\u548c<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/last-stone-weight-ii\/\">1049. \u6700\u540e\u4e00\u5757\u77f3\u5934\u7684\u91cd\u91cf II<\/a><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u5b8c\u5168\u80cc\u5305\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/leetcode.cn\/problems\/climbing-stairs\/\">70. \u722c\u697c\u68af<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/word-break\/\">139. \u5355\u8bcd\u62c6\u5206<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/perfect-squares\/\">279. \u5b8c\u5168\u5e73\u65b9\u6570<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/coin-change\/\">322. \u96f6\u94b1\u5151\u6362<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/combination-sum-iv\/\">377. \u7ec4\u5408\u603b\u548c \u2163<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/coin-change-ii\/\">518. \u96f6\u94b1\u5151\u6362 II<\/a><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u591a\u91cd\u80cc\u5305<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u6253\u5bb6\u52ab\u820d\u95ee\u9898<\/strong>\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/leetcode.cn\/problems\/house-robber\/\">198. \u6253\u5bb6\u52ab\u820d<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/house-robber-ii\/\">213. \u6253\u5bb6\u52ab\u820d II<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/house-robber-iii\/\">337. \u6253\u5bb6\u52ab\u820d III<\/a><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u80a1\u7968\u95ee\u9898<\/strong>\n<ul class=\"wp-block-list\">\n<li>\u53ea\u80fd\u4e70\u5356\u4e00\u6b21<a href=\"https:\/\/leetcode.cn\/problems\/best-time-to-buy-and-sell-stock\/\">121. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a<\/a><\/li>\n\n\n\n<li>\u53ef\u4ee5\u4e70\u5356\u591a\u6b21<a href=\"https:\/\/leetcode.cn\/problems\/best-time-to-buy-and-sell-stock-ii\/\">122. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a II<\/a><\/li>\n\n\n\n<li>\u6700\u591a\u4e70\u5356\u4e24\u6b21<a href=\"https:\/\/leetcode.cn\/problems\/best-time-to-buy-and-sell-stock-iii\/\">123. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a III<\/a><\/li>\n\n\n\n<li>\u6700\u591a\u4e70\u5356k\u6b21<a href=\"https:\/\/leetcode.cn\/problems\/best-time-to-buy-and-sell-stock-iv\/\">188. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a IV<\/a><\/li>\n\n\n\n<li>\u4e70\u5356\u591a\u6b21\uff0c\u5356\u51fa\u6709\u4e00\u5929\u51b7\u5374\u671f<a href=\"https:\/\/leetcode.cn\/problems\/best-time-to-buy-and-sell-stock-with-cooldown\/\">309. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a\u542b\u51b7\u51bb\u671f<\/a><\/li>\n\n\n\n<li>\u4e70\u5356\u591a\u6b21\uff0c\u6bcf\u6b21\u90fd\u6709\u624b\u7eed\u8d39<a href=\"https:\/\/leetcode.cn\/problems\/best-time-to-buy-and-sell-stock-with-transaction-fee\/\">714. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a\u542b\u624b\u7eed\u8d39<\/a><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u5b50\u5e8f\u5217\u95ee\u9898<\/strong>\n<ul class=\"wp-block-list\">\n<li>\u5b50\u5e8f\u5217(\u4e0d\u8fde\u7eed)\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/leetcode.cn\/problems\/longest-increasing-subsequence\/\">300. \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/uncrossed-lines\/\">1035. \u4e0d\u76f8\u4ea4\u7684\u7ebf<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/longest-common-subsequence\/\">1143. \u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217<\/a><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u5b50\u5e8f\u5217(\u8fde\u7eed)\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/leetcode.cn\/problems\/maximum-subarray\/\">53. \u6700\u5927\u5b50\u6570\u7ec4\u548c<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/longest-continuous-increasing-subsequence\/\">674. \u6700\u957f\u8fde\u7eed\u9012\u589e\u5e8f\u5217<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/maximum-length-of-repeated-subarray\/\">718. \u6700\u957f\u91cd\u590d\u5b50\u6570\u7ec4<\/a><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u7f16\u8f91\u8ddd\u79bb\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/leetcode.cn\/problems\/edit-distance\/\">72. \u7f16\u8f91\u8ddd\u79bb<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/distinct-subsequences\/\">115. \u4e0d\u540c\u7684\u5b50\u5e8f\u5217<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/is-subsequence\/\">392. \u5224\u65ad\u5b50\u5e8f\u5217<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/delete-operation-for-two-strings\/\">583. \u4e24\u4e2a\u5b57\u7b26\u4e32\u7684\u5220\u9664\u64cd\u4f5c<\/a><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u56de\u6587\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/leetcode.cn\/problems\/longest-palindromic-subsequence\/\">516. \u6700\u957f\u56de\u6587\u5b50\u5e8f\u5217<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.cn\/problems\/palindromic-substrings\/\">647. \u56de\u6587\u5b50\u4e32<\/a><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h1 class=\"wp-block-heading\">\u57fa\u7840\u9898\u76ee<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/unique-paths\/\">62. \u4e0d\u540c\u8def\u5f84<\/a>\u2705<\/h2>\n\n\n\n<p><em><strong>Solution1\uff1a\u9012\u5f52\u56de\u6eaf\u641c\u7d22\uff08\u4e00\u5f00\u59cb\u8d85\u5185\u5b58\uff0c\u540e\u7cbe\u7b80\u53d8\u91cf\uff0c\u4f46\u8d85\u65f6\uff0c\u53ea\u80fd\u8fc7\u6837\u4f8b\uff0c\u9042\u653e\u5f03\uff09\uff08\u539f\u56e0\uff1a\u56de\u6eaf\u641c\u7d22\u672c\u8d28\u4e0a\u662f\u66b4\u529b\uff09<\/strong><\/em><\/p>\n\n\n\n<p><em><strong>Solution2\uff1a\u52a8\u6001\u89c4\u5212\uff08\u8be6\u89c1\u6ce8\u91ca\uff09<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution1 {\nprivate:\n    \/\/ vector&lt;string&gt; res; \/\/\u5176\u5b9e\u53ea\u5b9a\u4e49\u4e00\u4e2a\u53d8\u91cf\u6765\u8bb0\u5f55\u65b9\u6848\u6570\u5c31\u53ef\u4ee5\n    \/\/ string path; \/\/\u8fd9\u6837\u5b9a\u4e49\u53d8\u91cf\u662f\u4e3a\u4e86\u65b9\u4fbfdebug\n    int res;\n    vector&lt;vector&lt;int&gt;&gt; map;\npublic:\n    void backTracking(int row, int col, int m, int n) {\n        if(row == m-1 &amp;&amp; col == n-1) {\n            \/\/ res.push_back(path);\n            res++;\n            return ;\n        }\n\n        \/\/\u641c\u9898\u76ee\u7ed9\u7684\u4e24\u4e2a\u65b9\u5411\n        if(row != m-1 &amp;&amp; !map&#91;row+1]&#91;col]) { \/\/\u4e0b\n            map&#91;row+1]&#91;col] = 1;\n            \/\/ path += \"D\";\n            backTracking(row+1, col, m, n);\n            map&#91;row+1]&#91;col] = 0;\n            \/\/ path.erase(path.size()-1, 1);\n        }\n\n        if(col != n-1 &amp;&amp; !map&#91;row]&#91;col+1]) { \/\/\u53f3\n            map&#91;row]&#91;col+1] = 1;\n            \/\/ path += \"R\";\n            backTracking(row, col+1, m, n);\n            map&#91;row]&#91;col+1] = 0;\n            \/\/ path.erase(path.size()-1, 1);\n        }\n\n        \/\/\u6700\u540e\u8fd4\u56de\n        return ;\n    }\n    int uniquePaths(int m, int n) {\n        map = vector&lt;vector&lt;int&gt;&gt;(m, vector&lt;int&gt;(n, 0));\n        map&#91;0]&#91;0] = 1;\n        res = 0;\n\n        backTracking(0, 0, m, n);\n        \n        \/\/ for(const auto &amp;i : res) cout &lt;&lt; i &lt;&lt; endl;\n\n        \/\/ return res.size();\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution2 {\npublic:\n    int uniquePaths(int m, int n) {\n        vector&lt;vector&lt;int&gt;&gt; dp(m, vector&lt;int&gt;(n, 0)); \/\/\u8868\u793a\u8d70\u5230\u5750\u6807\u4e3a(i, j)\u7684\u4f4d\u7f6e\u6709dp&#91;i]&#91;j]\u79cd\u4e0d\u540c\u8def\u5f84\n        \n        \/\/\u521d\u59cb\u5316\n        for(int i = 0; i &lt; m; i++) dp&#91;i]&#91;0] = 1;\n        for(int i = 0; i &lt; n; i++) dp&#91;0]&#91;i] = 1;\n\n        for(int i = 1; i &lt; m; i++) {\n            for(int j = 1; j &lt; n; j++) {\n                dp&#91;i]&#91;j] = dp&#91;i-1]&#91;j] + dp&#91;i]&#91;j-1]; \/\/\u8981\u4e0d\u4ece\u4e0a\u4e00\u683c\u8fc7\u6765 \u8981\u4e0d\u4ece\u5de6\u4e00\u683c\u8fc7\u6765\n                cout &lt;&lt; \"dp&#91;\" &lt;&lt; i &lt;&lt; \"]&#91;\" &lt;&lt; j &lt;&lt; \"] = \" &lt;&lt; dp&#91;i]&#91;j] &lt;&lt; endl;\n            }\n        }\n\n        return dp&#91;m-1]&#91;n-1];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/unique-paths-ii\/\">63. \u4e0d\u540c\u8def\u5f84 II<\/a>\u2705<\/h2>\n\n\n\n<p><strong><em>\u641c\u7d22\u4f1a\u8d85\u65f6\uff0c\u4f9d\u7136\u52a8\u6001\u89c4\u5212<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u4e0e\u4e0a\u9898\u7c7b\u4f3c\uff0c\u53ea\u662f\u521d\u59cb\u5316\u590d\u6742\u4e00\u70b9\uff0c\u518d\u628a\u969c\u788d\u4f4d\u7f6e\u7684dp[i][j]\u8bbe\u4e3a0\u5373\u53ef<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int uniquePathsWithObstacles(vector&lt;vector&lt;int&gt;&gt;&amp; obstacleGrid) {\n        int m = obstacleGrid.size();\n        int n = obstacleGrid&#91;0].size();\n\n        vector&lt;vector&lt;int&gt;&gt; dp(m, vector&lt;int&gt;(n, 0)); \/\/\u8868\u793a\u8d70\u5230\u5750\u6807\u4e3a(i, j)\u7684\u4f4d\u7f6e\u6709dp&#91;i]&#91;j]\u79cd\u4e0d\u540c\u8def\u5f84\n        \n        \/\/\u521d\u59cb\u5316\n        int firstCol_pos = m;\n        int firstRow_pos = n;\n        for(int i = 0; i &lt; m; i++) { \/\/\u5bfb\u627e\u7b2c\u4e00\u5217\u7684\u7b2c\u4e00\u4e2a\u969c\u788d\u4f4d\u7f6e\n            if(obstacleGrid&#91;i]&#91;0]) {\n                firstCol_pos = i; \n                break;\n            }\n        }\n        for(int i = 0; i &lt; n; i++) { \/\/\u5bfb\u627e\u7b2c\u4e00\u884c\u7684\u7b2c\u4e00\u4e2a\u969c\u788d\u4f4d\u7f6e\n            if(obstacleGrid&#91;0]&#91;i]) {\n                firstRow_pos = i; \n                break;\n            }\n        }\n\n        for(int i = 0; i &lt; firstCol_pos; i++) dp&#91;i]&#91;0] = 1;\n        for(int i = 0; i &lt; firstRow_pos; i++) dp&#91;0]&#91;i] = 1;\n\n        for(int i = 1; i &lt; m; i++) {\n            for(int j = 1; j &lt; n; j++) {\n                if(obstacleGrid&#91;i]&#91;j]) dp&#91;i]&#91;j] = 0;\n                else dp&#91;i]&#91;j] = dp&#91;i-1]&#91;j] + dp&#91;i]&#91;j-1]; \/\/\u8981\u4e0d\u4ece\u4e0a\u4e00\u683c\u8fc7\u6765 \u8981\u4e0d\u4ece\u5de6\u4e00\u683c\u8fc7\u6765\n                cout &lt;&lt; \"dp&#91;\" &lt;&lt; i &lt;&lt; \"]&#91;\" &lt;&lt; j &lt;&lt; \"] = \" &lt;&lt; dp&#91;i]&#91;j] &lt;&lt; endl;\n            }\n        }\n\n        return dp&#91;m-1]&#91;n-1];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/climbing-stairs\/\">70. \u722c\u697c\u68af<\/a>\u2705<\/h2>\n\n\n\n<p><em><strong>dp\u6570\u7ec4\u4e0b\u6807\u4ee3\u8868\u5f53\u524d\u5728\u7b2c\u51e0\u9636\uff0c\u6570\u7ec4value\u8868\u793a\u5230\u8fd9\u4e00\u9636\u7684\u65b9\u6cd5\u6570<\/strong><\/em><strong><em>\uff08\u5373\u722c\u5230\u7b2ci\u5c42\u697c\u68af\uff0c\u6709dp[i]\u79cd\u65b9\u6cd5\uff09<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>\u904d\u5386\u987a\u5e8f\u4ece\u524d\u5f80\u540e \u4f46\u662f\u4e00\u5f00\u59cb\u6ca1\u60f3\u660e\u767d\u4e3a\u4ec0\u4e48\u72b6\u6001\u8f6c\u79fb\u516c\u5f0f\u662fdp[i] = dp[i-1] + dp[i-2]<\/em><\/strong> <strong><em>\u53ea\u662f\u627e\u89c4\u5f8b\u63a8\u51fa\u6765\u7684<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int climbStairs(int n) {\n        vector&lt;int&gt; dp(50); \/\/dp\u6570\u7ec4\u4e0b\u6807\u4ee3\u8868\u5f53\u524d\u5728\u7b2c\u51e0\u9636\uff0c\u6570\u7ec4value\u8868\u793a\u5230\u8fd9\u4e00\u9636\u7684\u65b9\u6cd5\u6570\n        dp&#91;1] = 1;\n        dp&#91;2] = 2;\n        if(n &lt; 3) return dp&#91;n];\n        for(int i = 3; i &lt;= n; i++) dp&#91;i] = dp&#91;i-1] + dp&#91;i-2];\n\n        return dp&#91;n];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/unique-binary-search-trees\/\">96. \u4e0d\u540c\u7684\u4e8c\u53c9\u641c\u7d22\u6811<\/a>\u274c<\/h2>\n\n\n\n<p><em><strong>\u60f3\u4e0d\u51fa\u72b6\u6001\u8f6c\u79fb\u516c\u5f0f<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int numTrees(int n) {\n        vector&lt;int&gt; dp(n + 1); \/\/\u8868\u793ai\u4e2a\u8282\u70b9\u7ec4\u6210\u7684\u4e0d\u76f8\u540cBST\u6709dp&#91;i]\u79cd\n        \/*\n        dp&#91;0] = \n        dp&#91;1] = 1\n        dp&#91;2] = 2\n        dp&#91;3] = 5\n        *\/\n\n        dp&#91;0] = 1;\n        for(int i = 1; i &lt;= n; i++) {\n            for(int j = 1; j &lt;= i; j++) {\n                dp&#91;i] += dp&#91;j - 1] * dp&#91;i - j];\n            }\n        }\n        \n        return dp&#91;n];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/integer-break\/\">343. \u6574\u6570\u62c6\u5206<\/a>\u274c<\/h2>\n\n\n\n<p><strong><em>Solution1\uff1a\u7b2c\u4e00\u53cd\u5e94\u662f\u56de\u6eaf\u641c\u7d22\uff0c\u4e0d\u51fa\u6240\u6599\u8d85\u65f6\u4e86\uff0c\u53ea\u80fd\u8fc7\u6837\u4f8b<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>Solution2\uff1aDP\uff08\u8be6\u89c1\u6ce8\u91ca\uff09<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution1 {\nprivate:\n    int res = 0;\n    int mul = 1;\npublic:\n    void backTracking(int n, int depth) {\n        \/\/ if(n &lt; 0) return ;\n        if(!n) {\n            res = max(res, mul);\n            cout &lt;&lt; \"mul = \" &lt;&lt; mul &lt;&lt; endl;\n            return ;\n        }\n        \/\/\u7b2c\u4e00\u5c42\u4e0d\u80fd\u53d6\u5230n \u56e0\u4e3a0*n\u4e3a0\n        for(int i = 1; i &lt;= n; i++) {\n            if(depth == 1 &amp;&amp; i == n) continue;\n            mul *= i;\n            backTracking(n - i, depth + 1);\n            mul \/= i;\n        }\n    }\n    int integerBreak(int n) {\n        backTracking(n, 1);\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution2 {    \npublic:\n    int integerBreak(int n) {\n        vector&lt;int&gt; dp(n + 1); \/\/\u8868\u793an\u4e3ai\u65f6\u7684\u6700\u5927\u4e58\u79ef\u662fdp&#91;i]\n\n        dp&#91;2] = 1;\n        \/\/ dp&#91;3] = 2;\n        \/\/ dp&#91;4] = 4\n      \n        for(int i = 3; i &lt;= n; i++) {\n            for(int j = 1; j &lt; i; j++) {\n                \/\/\u5bf9\u4e8e\u904d\u5386\u7684j\uff0c\u8981\u4e48\u628ai\u62c6\u5206\u4e3a\u4e24\u4efd\uff0c\u8981\u4e48\u7ee7\u7eed\u5f80\u524d\u62c6\n                \/\/\u5373j\u662f\u62c6\u5206i\u7684\u7b2c\u4e00\u4e2a\u6570\n                dp&#91;i] = max(dp&#91;i], max(j * (i - j), j * dp&#91;i - j]));\n            }\n        }\n\n        return dp&#91;n];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/fibonacci-number\/\">509. \u6590\u6ce2\u90a3\u5951\u6570<\/a>\u2705<\/h2>\n\n\n\n<p><strong><em>\u72b6\u6001\u8f6c\u79fb\u516c\u5f0f\u7ed9\u4e86\uff0c\u521d\u59cb\u5316\u7ed9\u4e86\uff0c\u904d\u5386\u4ece\u524d\u5f80\u540e\u5373\u53ef<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int fib(int n) {\n        int f&#91;35];\n        f&#91;0] = 0;\n        f&#91;1] = 1;\n\n        for(int i = 2; i &lt;= n; i++) f&#91;i] = f&#91;i-1] + f&#91;i-2];\n\n        return f&#91;n];\n    } \n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/min-cost-climbing-stairs\/\">746. \u4f7f\u7528\u6700\u5c0f\u82b1\u8d39\u722c\u697c\u68af<\/a>\u2705<\/h2>\n\n\n\n<p><strong><em>\u722c\u4e0a\u7b2ci\u9636\u697c\u68af\u7684\u6700\u5c0f\u8d39\u7528\u4e3adp[i]<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>\u72b6\u6001\u8f6c\u79fb\u516c\u5f0f\u4e3adp[i] = min(cost[i-1] + dp[i-1], cost[i-2] + dp[i-2]) \u56e0\u4e3a\u8981\u4e0d\u4ece\u4e0a\u4e00\u9636\u722c\u4e0a\u6765\uff0c\u8981\u4e0d\u4ece\u4e0a\u4e24\u9636\u722c\u4e0a\u6765\uff0c\u53ea\u8981\u652f\u4ed8\u4e86\u5f53\u65f6\u90a3\u9636\u7684\u8d39\u7528\u5373\u53ef\uff0c\u56e0\u6b64\u4ece\u4e24\u79cd\u9009\u62e9\u4e2d\u627e\u82b1\u8d39\u8f83\u5c0f\u7684<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u521d\u59cb\u5316\uff1a<\/strong><\/em><strong><em>&nbsp;dp[0] = 0; dp[1] = 0;<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u904d\u5386\u987a\u5e8f\u4ece\u524d\u5f80\u540e<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int minCostClimbingStairs(vector&lt;int&gt;&amp; cost) {\n        vector&lt;int&gt; dp(1005); \/\/\u722c\u4e0a\u7b2ci\u9636\u697c\u68af\u7684\u6700\u5c0f\u8d39\u7528\u4e3adp&#91;i]\n\n        dp&#91;0] = 0;\n        dp&#91;1] = 0;\n        for(int i = 2 ; i &lt;= cost.size(); i++) {\n            dp&#91;i] = min(cost&#91;i-1] + dp&#91;i-1], cost&#91;i-2] + dp&#91;i-2]);\n            cout &lt;&lt; \"i = \" &lt;&lt; i &lt;&lt; \", dp&#91;i] = \" &lt;&lt; dp&#91;i] &lt;&lt; endl;\n        }\n  \n        return dp&#91;cost.size()];\n\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h1 class=\"wp-block-heading\">\u80cc\u5305\u95ee\u9898<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/partition-equal-subset-sum\/\">416. \u5206\u5272\u7b49\u548c\u5b50\u96c6<\/a>\u2705<\/h2>\n\n\n\n<p><strong><em>01\u80cc\u5305\u5e94\u7528\u9898\uff1a\u4e00\u4e2a\u5143\u7d20\u53ea\u80fd\u9009\u4e00\u6b21\uff0c\u91cd\u91cf\u6570\u7ec4\u548c\u4ef7\u503c\u6570\u7ec4\u76f8\u540c\uff0c\u5982\u679c\u80fd\u7528\u96c6\u5408\u4e2d\u7684\u5143\u7d20\u6b63\u597d\u586b\u6ee1\u5bb9\u91cf\u4e3asum\/2\u7684\u80cc\u5305\uff0c\u5373dp[j] = j\uff0c\u5219\u8fd4\u56detrue<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    bool canPartition(vector&lt;int&gt;&amp; nums) {\n        int sum = 0;\n        for(const auto &amp;i : nums) sum += i;\n        if(sum % 2) return false;\n        sum \/= 2;\n\n        vector&lt;int&gt; dp(sum + 1);\n        dp&#91;0] = 0;\n\n        for(int i = 0; i &lt; nums.size(); i++) {\n            for(int j = sum; j &gt;= nums&#91;i]; j--) {\n                dp&#91;j] = max(dp&#91;j], dp&#91;j - nums&#91;i]] + nums&#91;i]);\n                if(i == nums.size()-1) cout &lt;&lt; \"dp&#91;\" &lt;&lt; j &lt;&lt; \"] = \" &lt;&lt; dp&#91;j] &lt;&lt; endl;\n            }\n        }\n\n        if(dp&#91;sum] == sum) return true;\n        else return false;\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/ones-and-zeroes\/\">474. \u4e00\u548c\u96f6<\/a>\u274c<\/h2>\n\n\n\n<p><strong><em>\u4e24\u4e2a\u7ef4\u5ea6\u768401\u80cc\u5305<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>\u6700\u591a\u6709i\u4e2a0\u548cj\u4e2a1\u7684strs\u7684\u6700\u5927\u5b50\u96c6\u7684\u5927\u5c0f\u4e3adp[i][j]<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int findMaxForm(vector&lt;string&gt;&amp; strs, int m, int n) {\n        vector&lt;vector&lt;int&gt;&gt; dp(m + 1, vector&lt;int&gt; (n + 1, 0)); \n        for(const auto &amp;str : strs) { \/\/\u904d\u5386\u7269\u54c1\n            int oneNum = 0, zeroNum = 0;\n            for(const auto &amp;c : str) {\n                if(c == '0') zeroNum++;\n                else oneNum++;\n            }\n            for(int i = m; i &gt;= zeroNum; i--) { \/\/\u904d\u5386\u80cc\u5305\u5bb9\u91cf\u4e14\u4ece\u540e\u5411\u524d\u904d\u5386\n                for(int j = n; j &gt;= oneNum; j--) {\n                    dp&#91;i]&#91;j] = max(dp&#91;i]&#91;j], dp&#91;i - zeroNum]&#91;j - oneNum] + 1);\n                    \/\/ cout &lt;&lt; \"str = \" &lt;&lt; str &lt;&lt; \" dp&#91;\" &lt;&lt; i &lt;&lt; \"]&#91;\" &lt;&lt; j &lt;&lt; \"] = \" &lt;&lt; dp&#91;i]&#91;j] &lt;&lt; endl;\n                }\n            }\n        }\n\n        return dp&#91;m]&#91;n];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/target-sum\/\">494. \u76ee\u6807\u548c<\/a>\u274c<\/h2>\n\n\n\n<p><em><strong>\u4e0d\u662f\u6c42\u80cc\u5305\u91cc\u6700\u591a\u80fd\u88c5\u591a\u5c11\u4e86\uff0c\u800c\u662f\u80cc\u5305\u88c5\u6ee1\u6709\u591a\u5c11\u79cd\u65b9\u6cd5<\/strong><\/em><\/p>\n\n\n\n<p><em><strong>\u8be6\u89c1\u9898\u89e3\uff1a<a href=\"https:\/\/programmercarl.com\/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html#%E6%80%9D%E8%B7%AF\">https:\/\/programmercarl.com\/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html#%E6%80%9D%E8%B7%AF<\/a><\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int findTargetSumWays(vector&lt;int&gt;&amp; nums, int target) {\n       int sum = 0;\n       for(const auto &amp;i : nums) sum += i;\n       int bag = (target + sum) \/ 2;\n\n       if((target + sum) % 2 == 1) return 0;\n       if(abs(target) &gt; sum) return 0;\n\n       vector&lt;int&gt; dp(bag + 1, 0);\n       dp&#91;0] = 1;\n       for(int i = 0; i &lt; nums.size(); i++) {\n            for(int j = bag; j &gt;= nums&#91;i]; j--) {\n                dp&#91;j] += dp&#91;j - nums&#91;i]];\n            }\n       }\n\n       return dp&#91;bag];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/last-stone-weight-ii\/\">1049. \u6700\u540e\u4e00\u5757\u77f3\u5934\u7684\u91cd\u91cf II<\/a>\u274c<\/h2>\n\n\n\n<p><strong><em>\u4e0d\u77e5\u9053\u600e\u4e48\u5e94\u7528\u523001\u80cc\u5305<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>\u77f3\u5934\u7684\u91cd\u91cf\u548c\u4ef7\u503c\u7b49\u540c\uff0cdp[j]\u8868\u793a\u5f53\u80cc\u5305\u5bb9\u91cf\u4e3aj\u65f6\u6240\u80fd\u5bb9\u7eb3\u7684\u77f3\u5934\u603b\u91cd\u91cf\uff0c\u628a\u80cc\u5305\u5bb9\u91cf\u5b9a\u4e3asum\/2\uff0c\u5219\u4e00\u5806\u77f3\u5934\u548c\u53e6\u4e00\u5806\u77f3\u5934\u7684\u91cd\u91cf\u5206\u522b\u662fdp[sum\/2]\u548csum &#8211; dp[sum\/2]<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int lastStoneWeightII(vector&lt;int&gt;&amp; stones) {\n        int sum = 0;\n        for(const auto &amp;i : stones) sum += i;\n        int bag = sum \/ 2;\n        cout &lt;&lt; \"sum = \" &lt;&lt; sum &lt;&lt; endl;\n        vector&lt;int&gt; dp(bag+1, 0);\n\n        for(int i = 0; i &lt; stones.size(); i++) {\n            for(int j = bag; j &gt;= stones&#91;i]; j--) {\n                dp&#91;j] = max(dp&#91;j], dp&#91;j-stones&#91;i]] + stones&#91;i]);\n                if(i == stones.size() - 1) cout &lt;&lt; \"dp&#91;\" &lt;&lt; j &lt;&lt; \"] = \" &lt;&lt; dp&#91;j] &lt;&lt; endl;\n            }\n        }\n\n        return sum - dp&#91;bag] - dp&#91;bag];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1067\">57. \u722c\u697c\u68af\uff08\u7b2c\u516b\u671f\u6a21\u62df\u7b14\u8bd5\uff09<\/a>\u2705<\/h2>\n\n\n\n<p>\u8ddf<a href=\"https:\/\/leetcode.cn\/problems\/combination-sum-iv\/\">377. \u7ec4\u5408\u603b\u548c \u2163<\/a>\u540c\u7406\uff0c\u4e00\u6b21\u8fc8\u4e00\u9636\u3001\u4e24\u9636\u3001n\u9636\u770b\u505a\u662f\u4e0d\u540c\u7684\u7269\u54c1\uff0c\u6bcf\u4e2a\u7269\u54c1\u53ef\u4ee5\u53d6\u591a\u6b21\uff0c\u6700\u540e\u6c42\u6392\u5217\u6570<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/word-break\/\">139. \u5355\u8bcd\u62c6\u5206<\/a>\u2705<\/h2>\n\n\n\n<p><strong><em>\u5355\u8bcd\u53ef\u4ee5\u91cd\u590d\u4f7f\u7528 \u60f3\u5230\u5b8c\u5168\u80cc\u5305<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>\u6570\u7ec4\u542b\u4e49\uff1a\u62fc\u51fa\u76ee\u6807\u5b57\u7b26\u4e32\u524di\u4e2a\u5b57\u7b26\u6240\u9700\u8981\u7684\u6700\u5c11\u5355\u8bcd\u6570\u4e3adp[i]<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u4e3a\u4e86\u80fd\u591a\u6b21\u9009\u5230\u91cd\u590d\u7684\u5355\u8bcd<strong><em>\uff08\u672c\u8d28\u4e0a\u662f\u6392\u5217\u95ee\u9898\uff1aaba\u548caab\u4e0d\u540c\uff09<\/em><\/strong>\uff0c\u56e0\u6b64\u5fc5\u987b\u5148\u904d\u5386\u80cc\u5305\u5bb9\u91cf\uff0c\u518d\u904d\u5386\u7269\u54c1<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    bool wordBreak(string s, vector&lt;string&gt;&amp; wordDict) {\n        vector&lt;uint64_t&gt; dp(s.size() + 1, INT_MAX);\n        dp&#91;0] = 0; \n\n        for(int i = 0; i &lt;= s.size(); i++) {\n            for(int j = 0; j &lt; wordDict.size(); j++) {\n                if(i &lt; wordDict&#91;j].size()) continue;\n                if(s.substr(i - wordDict&#91;j].size(), wordDict&#91;j].size()) == wordDict&#91;j]) {\n                    dp&#91;i] = min(dp&#91;i], dp&#91;i - wordDict&#91;j].size()] + 1);\n                }\n                \/\/ cout &lt;&lt; \"i = \" &lt;&lt; i &lt;&lt; \", j = \" &lt;&lt; j &lt;&lt; \", dp&#91;\" &lt;&lt; j &lt;&lt; \"] = \" &lt;&lt; dp&#91;j] &lt;&lt; endl;\n\n            }\n        }\n\n        if(dp&#91;s.size()] == INT_MAX) return false;\n        return true;\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/perfect-squares\/\">279. \u5b8c\u5168\u5e73\u65b9\u6570<\/a>\u2705<\/h2>\n\n\n\n<p><strong><em>\u6bcf\u4e2a\u5b8c\u5168\u5e73\u65b9\u6570\u90fd\u53ef\u4ee5\u91cd\u590d\u7528 \u60f3\u5230\u5b8c\u5168\u80cc\u5305<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u6c42\u6700\u5c11\u6570\u91cf \u8ddf<a href=\"https:\/\/leetcode.cn\/problems\/coin-change\/\">322. \u96f6\u94b1\u5151\u6362<\/a>\u5f88\u76f8\u4f3c \u53ea\u9700\u8981\u628a\u7269\u54c1\u4ece\u786c\u5e01\u6362\u6210\u5b8c\u5168\u5e73\u65b9\u6570\u5373\u53ef<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int numSquares(int n) {\n        \/\/\u5f53n\u4e3ai\u65f6\uff0c\u51d1\u6ee1n\u9700\u8981\u7684\u6700\u5c11\u5b8c\u5168\u5e73\u65b9\u6570\u4e3adp&#91;i]\n        vector&lt;int&gt; dp(n + 1, INT_MAX);\n        dp&#91;0] = 0;\n\n        \/\/\u56e0\u4e3a1 &lt;= n &lt;= 10000\uff0c\u503c\u4e0d\u5927\uff0c\u56e0\u6b64\u53ef\u4ee5\u4e8b\u5148\u51c6\u5907\u4e00\u4e2a\u5b8c\u5168\u5e73\u65b9\u6570\u6570\u7ec4\n        vector&lt;int&gt; nums;\n        for(int i = 1; i * i &lt;= n; i++) nums.push_back(i * i);\n\n        for(int i = 0; i &lt; nums.size(); i++) {\n            for(int j = nums&#91;i]; j &lt;= n; j++) {\n                dp&#91;j] = min(dp&#91;j], dp&#91;j - nums&#91;i]] + 1);\n            }\n        }\n\n        return dp&#91;n];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/coin-change\/\">322. \u96f6\u94b1\u5151\u6362<\/a>\u274c<\/h2>\n\n\n\n<p><strong><em>\u5173\u952e\u8bcd\uff1a\u6bcf\u79cd\u786c\u5e01\u6570\u91cf\u65e0\u9650 \u60f3\u5230\u5b8c\u5168\u80cc\u5305<\/em><\/strong> <strong><em> \u4f46\u662f\u8981\u53d8\u5f0f<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u5f53\u603b\u91d1\u989d\u4e3ai\u65f6\uff0c\u51d1\u6ee1\u603b\u91d1\u989d\u9700\u8981\u7684\u6700\u5c11\u786c\u5e01\u4e2a\u6570\u4e3adp[i]<\/strong><\/em><\/p>\n\n\n\n<p><strong><em>dp\u6570\u7ec4\u5b9a\u4e49 \u9012\u63a8\u516c\u5f0f dp[0]\u521d\u59cb\u5316\u90fd\u5bf9\u4e86 \u4f46\u662fdp\u5176\u4ed6\u5143\u7d20\u7684\u521d\u59cb\u5316\u9519\u4e86 \u5e94\u8be5\u662f\u4e00\u4e2a\u6700\u5927\u7684\u6570 <\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int coinChange(vector&lt;int&gt;&amp; coins, int amount) {\n        vector&lt;uint64_t&gt; dp(amount + 1, INT_MAX);\n        dp&#91;0] = 0;\n\n        for(int i = 0; i &lt; coins.size(); i++) {\n            for(int j = coins&#91;i]; j &lt;= amount; j++) {\n                dp&#91;j] = min(dp&#91;j], dp&#91;j - coins&#91;i]] + 1);\n                \/\/ cout &lt;&lt; \"i = \" &lt;&lt; i &lt;&lt; \", j = \" &lt;&lt; j &lt;&lt; \", dp&#91;\" &lt;&lt; j &lt;&lt; \"] = \" &lt;&lt; dp&#91;j] &lt;&lt; endl;\n            }\n        }\n\n        if(dp&#91;amount] == INT_MAX) return -1;\n        return dp&#91;amount];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/combination-sum-iv\/\">377. \u7ec4\u5408\u603b\u548c \u2163<\/a>\u274c<\/h2>\n\n\n\n<p><strong><em>\u4e4b\u524d\u7684\u7ec4\u5408\u603b\u548c123\u90fd\u80fd\u7528\u56de\u6eaf\u641c\u7d22\u5904\u7406 \u4f46\u8fd9\u4e2a\u4f1a\u8d85\u65f6 \u56e0\u6b64\u52a8\u6001\u89c4\u5212<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>\u6bcf\u4e2a\u5143\u7d20\u90fd\u53ef\u4ee5\u53d6\u65e0\u6570\u6b21 \u800c\u4e14\u6700\u7ec8\u6c42\u7684\u662f\u6392\u5217\u79cd\u6570 \u56e0\u6b64\u76f4\u63a5\u5957\u5b8c\u5168\u80cc\u5305\u6c42\u6392\u5217\u79cd\u6570\u6a21\u677f<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int combinationSum4(vector&lt;int&gt;&amp; nums, int target) {\n        vector&lt;uint64_t&gt; dp(target + 1, 0);\n        dp&#91;0] = 1;\n\n        for(int i = 0; i &lt;= target; i++) {\n            for(int j = 0; j &lt; nums.size(); j++) {\n                if(i - nums&#91;j] &gt;= 0) dp&#91;i] += dp&#91;i - nums&#91;j]];\n            }\n        }\n     \n        return dp&#91;target];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/coin-change-ii\/\">518. \u96f6\u94b1\u5151\u6362 II<\/a>\u2705<\/h2>\n\n\n\n<p><strong><em>\u5b8c\u5168\u80cc\u5305\u95ee\u9898\uff1a\u786c\u5e01\u7684weight\u7b49\u540cvalue\uff0c\u5f53\u80cc\u5305\u5bb9\u91cf\u4e3ai\u65f6\uff0c\u88c5\u6ee1\u80cc\u5305\u7684\u4e0d\u540c\u7ec4\u5408\u6570\u4e3adp[i]<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>uint64_t\u8868\u793a64\u4f4d\u65e0\u7b26\u53f7\u6574\u578b<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int change(int amount, vector&lt;int&gt;&amp; coins) {\n        vector&lt;uint64_t&gt; dp(amount + 1, 0); \/\/\u65e0\u7b26\u53f764\u4f4d\u6574\u578b  \n\n        dp&#91;0] = 1;\n        for(int i = 0; i &lt; coins.size(); i++) {\n            for(int j = coins&#91;i]; j &lt;= amount; j++) {\n                dp&#91;j] += dp&#91;j - coins&#91;i]];\n            }\n        }\n\n        return dp&#91;amount];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h1 class=\"wp-block-heading\">\u6253\u5bb6\u52ab\u820d<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/house-robber\/\">198. \u6253\u5bb6\u52ab\u820d<\/a>\u274c<\/h2>\n\n\n\n<p><strong><em>dp\u6570\u7ec4\u542b\u4e49\uff1a\u524di\u95f4\u623f\u5c4b\u80fd\u5077\u7684\u6700\u9ad8\u91d1\u989d\u4e3adp[i]<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u521d\u59cb\u5316\uff1adp[0]=nums[0]\uff08\u4e0b\u6807\u4e3a0\u4e5f\u5c31\u662f\u7b2c\u4e00\u95f4\u623f\u5c4b\uff0c\u80fd\u5077\u7684\u6700\u9ad8\u91d1\u989d\u81ea\u7136\u4e3anums[0]\uff09\uff0cdp[1] = max(nums[0], nums[1])\uff08\u76f8\u90bb\u7684\u4e24\u95f4\u623f\u53ea\u80fd\u5077\u4e00\u4e2a\uff0c\u56e0\u6b64\u54ea\u4e2a\u91d1\u989d\u9ad8\u5c31\u5077\u54ea\u4e2a\uff09<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int rob(vector&lt;int&gt;&amp; nums) {\n        if(nums.size() == 1) return nums&#91;0];\n\n        vector&lt;uint64_t&gt; dp(nums.size() + 1, 0);\n        dp&#91;0] = nums&#91;0];\n        dp&#91;1] = max(nums&#91;0], nums&#91;1]);\n\n        for(int i = 2; i &lt; nums.size(); i++) {\n            dp&#91;i] = max(dp&#91;i - 2] + nums&#91;i], dp&#91;i - 1]); \/\/\u7b2ci\u5bb6\u5077or\u4e0d\u5077\n            \/\/ cout &lt;&lt; \"dp&#91;\" &lt;&lt; i &lt;&lt; \"] = \" &lt;&lt; dp&#91;i] &lt;&lt; endl;\n        }\n\n        return dp&#91;nums.size()-1];   \n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/house-robber-ii\/\">213. \u6253\u5bb6\u52ab\u820d II<\/a>\u274c<\/h2>\n\n\n\n<p><em><strong>\u4e0d\u77e5\u9053\u600e\u4e48\u521d\u59cb\u5316dp\u6570\u7ec4<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int rob(vector&lt;int&gt;&amp; nums) {\n        if(nums.size() == 1) return nums&#91;0];\n        return max(robRange(0, nums.size() - 2, nums), robRange(1, nums.size() - 1, nums));\n    }\n    int robRange(int start, int end, vector&lt;int&gt;&amp; nums) {\n        if(start == end) return nums&#91;start];\n        vector&lt;int&gt; dp(nums.size() + 1, 0);\n        dp&#91;start] = nums&#91;start];\n        dp&#91;start+1] = max(nums&#91;start], nums&#91;start+1]);\n\n        for(int i = start + 2; i &lt;= end; i++) {\n            dp&#91;i] = max(dp&#91;i-1], dp&#91;i-2] + nums&#91;i]);\n        }\n        return dp&#91;end];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/house-robber-iii\/\">337. \u6253\u5bb6\u52ab\u820d III<\/a>\u274c<\/h2>\n\n\n\n<p><em><strong>\u7b80\u5355\u5730\u60f3\u6210\u4e86\u5c42\u5e8f\u904d\u5386\uff0c\u4ee5\u5c42\u4e3a\u5355\u4f4d\u5077\uff0c\u4f46\u5b9e\u9645\u4e0a\u5728\u4e00\u5c42\u4e2d\u53ef\u4ee5\u5077\u5176\u4e2d\u51e0\u4e2a\uff0c\u800c\u4e0d\u662f\u5168\u5077\u6216\u5168\u4e0d\u5077<\/strong><\/em><\/p>\n\n\n\n<p><strong><em>\u6811\u5f62DP<\/em><\/strong> <strong><em>\u9700\u8981\u9012\u5f52\u540e\u5e8f\u904d\u5386<\/em><\/strong> <em><strong>\u4f7f\u7528\u4e00\u4e2a\u957f\u5ea6\u4e3a2\u7684\u6570\u7ec4\uff0c\u8bb0\u5f55\u5f53\u524d\u8282\u70b9\u5077\u4e0e\u4e0d\u5077\u6240\u5f97\u5230\u7684\u7684\u6700\u5927\u91d1\u94b1<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int rob(TreeNode* root) {\n        vector&lt;int&gt; res = robTree(root);\n        return max(res&#91;0], res&#91;1]);\n    }\n    \/\/\u957f\u5ea6\u4e3a2\u7684\u6570\u7ec4\uff1a\u4e0b\u68070\u4ee3\u8868\u4e0d\u5077 1\u4ee3\u8868\u5077\n    vector&lt;int&gt; robTree(TreeNode* cur) {\n        if(!cur) return vector&lt;int&gt;{0, 0};\n        vector&lt;int&gt; left = robTree(cur-&gt;left);\n        vector&lt;int&gt; right = robTree(cur-&gt;right);\n        \/\/\u5077cur \u90a3\u4e48\u5c31\u4e0d\u80fd\u5077\u5de6\u53f3\u8282\u70b9 \n        int val1 = cur-&gt;val + left&#91;0] + right&#91;0];\n        \/\/\u4e0d\u5077cur \u90a3\u4e48\u53ef\u4ee5\u5077\u4e5f\u53ef\u4ee5\u4e0d\u5077\u5de6\u53f3\u8282\u70b9 \u53d6\u8f83\u5927\u7684\u60c5\u51b5\n        int val2 = max(left&#91;0], left&#91;1]) + max(right&#91;0], right&#91;1]);\n        return {val2, val1};\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h1 class=\"wp-block-heading\">\u80a1\u7968\u95ee\u9898<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/best-time-to-buy-and-sell-stock\/\">121. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a<\/a>\u274c<\/h2>\n\n\n\n<p><strong>\u53ea\u80fd\u4e70\u5356\u4e00\u6b21<\/strong><\/p>\n\n\n\n<p><em><strong>Solution1\uff1a\u8d2a\u5fc3 \u904d\u5386\u7ef4\u62a4\u5de6\u8fb9\u6700\u5c0f\u503c\u4e0e\u53f3\u8fb9\u6700\u5927\u503c<\/strong><\/em><\/p>\n\n\n\n<p><strong><em>Solution2\uff1aDP<\/em><\/strong> <strong><em>\u4e0d\u4f1a\u5b9a\u4e49\u6b64\u7c7b\u9898\u7684<\/em><\/strong><strong style=\"font-style: italic;\"><em>\u6570\u7ec4\u542b\u4e49<\/em><\/strong><\/p>\n\n\n\n<p><strong style=\"font-style: italic;\">\u6570\u7ec4\u542b\u4e49\uff1adp[i][0] \u8868\u793a\u7b2ci\u5929\u6301\u6709\u80a1\u7968\u6240\u5f97\u6700\u591a\u73b0\u91d1<\/strong> <strong><em>dp[i][1] \u8868\u793a\u7b2ci\u5929\u4e0d\u6301\u6709\u80a1\u7968\u6240\u5f97\u6700\u591a\u73b0\u91d1<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>\u9012\u63a8\u516c\u5f0f\uff1a<\/em><\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>dp[i][0] = max(dp[i-1][0], &#8211; prices[i]); \/\/i-1\u5929\u7684\u65f6\u5019\u5c31\u5df2\u7ecf\u6301\u6709 or \u7b2ci\u5929\u4e70\u5165<\/li>\n\n\n\n<li>dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]); \/\/i-1\u5929\u7684\u65f6\u5019\u5c31\u5df2\u7ecf\u4e0d\u6301\u6709 or \u7b2ci\u5929\u5356\u51fa<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution1 {\npublic:\n    int maxProfit(vector&lt;int&gt;&amp; prices) {\n        int low = INT_MAX;\n        int res = 0;\n        for(int i = 0; i &lt; prices.size(); i++) {\n            low = min(low, prices&#91;i]);\n            res = max(res, prices&#91;i] - low);\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution2 {\npublic:\n    int maxProfit(vector&lt;int&gt;&amp; prices) {\n        vector&lt;vector&lt;int&gt;&gt; dp(prices.size() + 1, vector&lt;int&gt;(2, 0));\n        \/\/dp&#91;i]&#91;0] \u8868\u793a\u7b2ci\u5929\u6301\u6709\u80a1\u7968\u6240\u5f97\u6700\u591a\u73b0\u91d1 \n        \/\/dp&#91;i]&#91;1] \u8868\u793a\u7b2ci\u5929\u4e0d\u6301\u6709\u80a1\u7968\u6240\u5f97\u6700\u591a\u73b0\u91d1\n        dp&#91;0]&#91;0] = 0 - prices&#91;0];\n        dp&#91;0]&#91;1] = 0;\n        cout &lt;&lt; \"dp&#91;0]&#91;0] = \" &lt;&lt; dp&#91;0]&#91;0] &lt;&lt; \" dp&#91;0]&#91;1] = \" &lt;&lt; dp&#91;0]&#91;1] &lt;&lt; endl;\n        for(int i = 1; i &lt; prices.size(); i++) {\n            dp&#91;i]&#91;0] = max(dp&#91;i-1]&#91;0], - prices&#91;i]); \/\/i-1\u5929\u7684\u65f6\u5019\u5c31\u5df2\u7ecf\u6301\u6709 or \u7b2ci\u5929\u4e70\u5165\n            dp&#91;i]&#91;1] = max(dp&#91;i-1]&#91;1], dp&#91;i-1]&#91;0] + prices&#91;i]); \/\/i-1\u5929\u7684\u65f6\u5019\u5c31\u5df2\u7ecf\u4e0d\u6301\u6709 or \u7b2ci\u5929\u5356\u51fa\n            \/\/ cout &lt;&lt; \"dp&#91;\" &lt;&lt; i &lt;&lt; \"]&#91;0] = \" &lt;&lt; dp&#91;i]&#91;0] &lt;&lt; \" dp&#91;\" &lt;&lt; i &lt;&lt; \"]&#91;1] = \" &lt;&lt; dp&#91;i]&#91;1] &lt;&lt; endl;\n        }\n\n        return dp&#91;prices.size()-1]&#91;1];\n    }\n};<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/best-time-to-buy-and-sell-stock-ii\/\">122. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a II<\/a>\u2705<\/h2>\n\n\n\n<p><strong>\u53ef\u4ee5\u4e70\u5356\u4efb\u610f\u6b21<\/strong><\/p>\n\n\n\n<p><strong><em>Solution1\uff1a\u8d2a\u5fc3\uff08\u53ea\u8981\u540e\u4e00\u5929\u6bd4\u5f53\u524d\u4ef7\u9ad8\uff0c\u5c31\u4e70\u4e86\u518d\u5356\uff09<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>Solution1\uff1aDP\uff08\u7c7b\u4f3c\u4e0a\u9898\uff0c\u4f46\u6ce8\u610f\u5728dp[i][0]\u7684\u9012\u63a8\u516c\u5f0f\u4e0a\u7565\u6709\u4e0d\u540c\uff0c\u56e0\u4e3a\u4e0a\u9898\u53ea\u80fd\u4e70\u5356\u4e00\u6b21\uff0c\u6ca1\u79ef\u7d2f\u73b0\u91d1\uff09<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution1 {  \npublic:\n    int maxProfit(vector&lt;int&gt;&amp; prices) {\n        int res = 0;\n        if(prices.size() == 1) return 0;\n        for(int i = 0; i &lt; prices.size() - 1; i++) {\n            if(prices&#91;i] &lt; prices&#91;i+1]) {\n                res += prices&#91;i+1] - prices&#91;i];\n            }\n        }\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution2 { \npublic:\n    int maxProfit(vector&lt;int&gt;&amp; prices) {\n        vector&lt;vector&lt;int&gt;&gt; dp(prices.size()+1, vector&lt;int&gt;(2, 0));\n        \/\/dp&#91;i]&#91;0]\u8868\u793a\u7b2ci\u5929\u6301\u6709\u80a1\u7968\u6240\u5f97\u6700\u591a\u73b0\u91d1 \n        \/\/dp&#91;i]&#91;1]\u8868\u793a\u7b2ci\u5929\u4e0d\u6301\u6709\u80a1\u7968\u6240\u5f97\u6700\u591a\u73b0\u91d1\n        dp&#91;0]&#91;0] = -prices&#91;0];\n        dp&#91;0]&#91;1] = 0;\n        \n        for(int i = 1; i &lt; prices.size(); i++) {\n            \/\/i-1\u5929\u7684\u65f6\u5019\u5c31\u5df2\u7ecf\u6301\u6709 or \u7b2ci\u5929\u4e70\u5165\uff08\u4e0e\u4e0a\u9898\u6709\u5dee\u5f02\uff0c\u56e0\u4e3a\u4e0a\u9898\u6ca1\u6709\u79ef\u7d2f\u73b0\u91d1\uff09\n            dp&#91;i]&#91;0] = max(dp&#91;i-1]&#91;0], dp&#91;i-1]&#91;1] - prices&#91;i]);\n            \/\/i-1\u5929\u7684\u65f6\u5019\u5c31\u5df2\u7ecf\u4e0d\u6301\u6709 or \u7b2ci\u5929\u5356\u51fa\n            dp&#91;i]&#91;1] = max(dp&#91;i-1]&#91;1], dp&#91;i-1]&#91;0] + prices&#91;i]);\n        }\n\n        return dp&#91;prices.size()-1]&#91;1];\n    }\n};<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/best-time-to-buy-and-sell-stock-iii\/\">123. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a III<\/a>\u274c<\/h2>\n\n\n\n<p><em><strong>\u96be\u70b9\u5728\u4e8e\u6700\u591a\u4e70\u5356\u4e24\u6b21\uff0c\u56e0\u6b64dp[i][0]\u3001dp[i][1]\u4e24\u4e2a\u72b6\u6001\u4e0d\u591f\u4e86<\/strong><\/em><\/p>\n\n\n\n<p><strong><em>dp\u6570\u7ec4\u542b\u4e49\uff1ai\u8868\u793a\u7b2ci\u5929\uff0cj\u4e3a0~3\u56db\u4e2a\u72b6\u6001\uff0cdp[i][j]\u8868\u793a\u7b2ci\u5929\u72b6\u6001j\u6240\u5269\u6700\u5927\u73b0\u91d1<\/em><\/strong><\/p>\n\n\n\n<ol start=\"0\" class=\"wp-block-list\">\n<li>\u7b2c\u4e00\u6b21\u6301\u6709\u80a1\u7968<\/li>\n\n\n\n<li>\u7b2c\u4e00\u6b21\u4e0d\u6301\u6709\u80a1\u7968<\/li>\n\n\n\n<li>\u7b2c\u4e8c\u6b21\u6301\u6709\u80a1\u7968<\/li>\n\n\n\n<li>\u7b2c\u4e8c\u6b21\u4e0d\u6301\u6709\u80a1\u7968<\/li>\n<\/ol>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int maxProfit(vector&lt;int&gt;&amp; prices) {\n        vector&lt;vector&lt;int&gt;&gt; dp(prices.size()+1, vector&lt;int&gt;(4, 0));\n        \/\/i\u8868\u793a\u7b2ci\u5929\uff0cj\u4e3a0~3\u56db\u4e2a\u72b6\u6001\uff0cdp&#91;i]&#91;j]\u8868\u793a\u7b2ci\u5929\u72b6\u6001j\u6240\u5269\u6700\u5927\u73b0\u91d1\n        \/\/\u72b6\u60010\u8868\u793a\u7b2c\u4e00\u6b21\u6301\u6709\u80a1\u7968\n        \/\/\u72b6\u60011\u8868\u793a\u7b2c\u4e00\u6b21\u4e0d\u6301\u6709\u80a1\u7968\n        \/\/\u72b6\u60012\u8868\u793a\u7b2c\u4e8c\u6b21\u6301\u6709\u80a1\u7968\n        \/\/\u72b6\u60013\u8868\u793a\u7b2c\u4e8c\u6b21\u4e0d\u6301\u6709\u80a1\u7968\n        dp&#91;0]&#91;0] = -prices&#91;0]; \n        dp&#91;0]&#91;2] = -prices&#91;0]; \n\n        for(int i = 1; i &lt; prices.size(); i++) {\n            dp&#91;i]&#91;0] = max(dp&#91;i-1]&#91;0], -prices&#91;i]);\n            dp&#91;i]&#91;1] = max(dp&#91;i-1]&#91;1], dp&#91;i-1]&#91;0] + prices&#91;i]);\n            dp&#91;i]&#91;2] = max(dp&#91;i-1]&#91;2], dp&#91;i-1]&#91;1] - prices&#91;i]);\n            dp&#91;i]&#91;3] = max(dp&#91;i-1]&#91;3], dp&#91;i-1]&#91;2] + prices&#91;i]);\n        }\n\n        return dp&#91;prices.size()-1]&#91;3];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/best-time-to-buy-and-sell-stock-iv\/\">188. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a IV<\/a><\/h2>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/best-time-to-buy-and-sell-stock-with-cooldown\/\">309. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a\u542b\u51b7\u51bb\u671f<\/a><\/h2>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/best-time-to-buy-and-sell-stock-with-transaction-fee\/\">714. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a\u542b\u624b\u7eed\u8d39<\/a><\/h2>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h1 class=\"wp-block-heading\">\u5b50\u5e8f\u5217\u95ee\u9898<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/longest-increasing-subsequence\/\">300. \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217<\/a>\u274c<\/h2>\n\n\n\n<p><strong>dp\u6570\u7ec4\u542b\u4e49\uff1adp[i]\u8868\u793ai\u4e4b\u524d(\u5305\u62eci)\u4ee5nums[i]\u7ed3\u5c3e\u7684\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int lengthOfLIS(vector&lt;int&gt;&amp; nums) {\n        int res = 1;\n        vector&lt;int&gt; dp(nums.size()+1, 1); \/\/\u4e0b\u6807\u4ece0\u5230i\u7684\u5143\u7d20\u7684\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u957f\u5ea6\u4e3adp&#91;i]\n        \n        for(int i = 1; i &lt; nums.size(); i++) {\n            for(int j = 0; j &lt; i; j++) {\n                if(nums&#91;i] &gt; nums&#91;j]) {\n                    dp&#91;i] = max(dp&#91;i], dp&#91;j] + 1); \n                }\n            }\n            res = max(res, dp&#91;i]);\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/uncrossed-lines\/\">1035. \u4e0d\u76f8\u4ea4\u7684\u7ebf<\/a><\/h2>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/longest-common-subsequence\/\">1143. \u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217<\/a><\/h2>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/maximum-subarray\/\">53. \u6700\u5927\u5b50\u6570\u7ec4\u548c<\/a><\/h2>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/longest-continuous-increasing-subsequence\/\">674. \u6700\u957f\u8fde\u7eed\u9012\u589e\u5e8f\u5217<\/a>\u2705<\/h2>\n\n\n\n<p><em><strong>\u6c42\u6700\u957f\u7684\u8fde\u7eed\u9012\u589e\u5b50\u5e8f\u5217\uff0c\u81ea\u7136\u60f3\u5230\u6ed1\u52a8\u7a97\u53e3<\/strong><\/em><\/p>\n\n\n\n<p><strong><em>\u4f46\u662fDP\u66f4\u7b80\u5355\uff0c\u76f8\u5f53\u4e8e<a href=\"https:\/\/leetcode.cn\/problems\/longest-increasing-subsequence\/\">300. \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217<\/a>\u7684\u7b80\u5355\u7248<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>\u4e5f\u53ef\u4ee5\u7528\u8d2a\u5fc3\uff0c\u66f4\u7b80\u5355<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int findLengthOfLCIS(vector&lt;int&gt;&amp; nums) {\n        int res = 1;\n        vector&lt;int&gt; dp(nums.size()+1, 1); \/\/\u4ee5\u4e0b\u6807i\u7684\u5143\u7d20\u7ed3\u5c3e\u7684\u6700\u957f\u9012\u589e\u5e8f\u5217\u957f\u5ea6\u4e3adp&#91;i]\n        \n        for(int i = 1; i &lt; nums.size(); i++) {\n            if(nums&#91;i] &gt; nums&#91;i-1]) {\n                dp&#91;i] = dp&#91;i-1] + 1; \n                \n            }\n            cout &lt;&lt; \"dp&#91;\" &lt;&lt; i &lt;&lt; \"] = \" &lt;&lt; dp&#91;i] &lt;&lt; endl;\n            res = max(res, dp&#91;i]);\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/maximum-length-of-repeated-subarray\/\">718. \u6700\u957f\u91cd\u590d\u5b50\u6570\u7ec4<\/a>\u274c<\/h2>\n\n\n\n<p><em><strong>\u7528\u4e8c\u7ef4\u6570\u7ec4\u8bb0\u5f55\u4e24\u4e2a\u5b57\u7b26\u4e32\u7684\u6240\u6709\u6bd4\u8f83\u60c5\u51b5<\/strong><\/em><\/p>\n\n\n\n<p><strong><em>dp\u6570\u7ec4\u542b\u4e49\uff1a\u4ee5\u4e0b\u6807i &#8211; 1\u4e3a\u7ed3\u5c3e\u7684A\uff0c\u548c\u4ee5\u4e0b\u6807j &#8211; 1\u4e3a\u7ed3\u5c3e\u7684B\uff0c\u6700\u957f\u91cd\u590d\u5b50\u6570\u7ec4\u957f\u5ea6\u4e3adp[i][j]<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>ps\uff1a\u4e3a\u4ec0\u4e48\u7528i-1\u800c\u4e0d\u662fi\uff1f\u8fd9\u6837dp[i][0] \u548cdp[0][j]\u90fd\u6ca1\u6709\u610f\u4e49\uff0c\u76f4\u63a5\u521d\u59cb\u5316\u4e3a0\uff0c\u800c\u4e0d\u7528\u989d\u5916\u521d\u59cb\u5316<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int findLength(vector&lt;int&gt;&amp; nums1, vector&lt;int&gt;&amp; nums2) {\n        \/\/\u4ee5\u4e0b\u6807i-1\u4e3a\u7ed3\u5c3e\u7684A\uff0c\u548c\u4ee5\u4e0b\u6807j-1\u4e3a\u7ed3\u5c3e\u7684B\uff0c\u6700\u957f\u91cd\u590d\u5b50\u6570\u7ec4\u957f\u5ea6\u4e3adp&#91;i]&#91;j]\n        vector&lt;vector&lt;int&gt;&gt; dp(nums1.size()+1, vector&lt;int&gt;(nums2.size()+1, 0));\n        int res = 0;\n        for(int i = 1; i &lt;= nums1.size(); i++) {\n            for(int j = 1; j &lt;= nums2.size(); j++) {\n                if(nums1&#91;i-1] == nums2&#91;j-1]) {\n                    dp&#91;i]&#91;j] = dp&#91;i-1]&#91;j-1] + 1;\n                }\n                \/\/ cout &lt;&lt; \"dp&#91;\" &lt;&lt; i &lt;&lt; \"]&#91;\" &lt;&lt; j &lt;&lt; \"] = \" &lt;&lt; dp&#91;i]&#91;j] &lt;&lt; endl;\n                res = max(res, dp&#91;i]&#91;j]);\n            }\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u203b<a href=\"https:\/\/leetcode.cn\/problems\/edit-distance\/\">72. \u7f16\u8f91\u8ddd\u79bb<\/a>\u274c<\/h2>\n\n\n\n<p><strong><em>dp\u6570\u7ec4\u542b\u4e49\uff1a\u4ee5\u4e0b\u6807i-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32word1\uff0c\u548c\u4ee5\u4e0b\u6807j-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32word2\uff0c\u6700\u8fd1\u7f16\u8f91\u8ddd\u79bb\u4e3adp[i][j]<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>\u6216\u8005\u53ef\u4ee5\u6362\u4e2a\u8bf4\u6cd5\uff1aword1\u4e2d\u524di\u4e2a\u5b57\u6bcd\u7ec4\u6210\u7684\u5b57\u7b26\u4e32\uff0c\u548cword2\u4e2d\u524dj\u4e2a\u5b57\u6bcd\u7ec4\u6210\u7684\u5b57\u7b26\u4e32\uff0c\u6700\u8fd1\u7f16\u8f91\u8ddd\u79bb\u4e3adp[i][j]\uff08\u56e0\u4e3a\u6bd4\u5982word=&#8221;abc&#8221;\uff0c\u5f53i=2\u65f6\uff0c\u5373\u4ee3\u8868\u4ee5\u4e0b\u6807i-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32\u201cab\u201d\uff0c\u4e5f\u5c31\u662f\u524di\u4e2a\u5b57\u6bcd\uff09<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u521d\u59cb\u5316\uff1adp[i][0]\uff1a\u4ee5\u4e0b\u6807i-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32word1\uff0c\u548c\u7a7a\u5b57\u7b26\u4e32word2\uff0c\u6700\u8fd1\u7f16\u8f91\u8ddd\u79bb\u4e3adp[i][0]\uff0c\u5373i\uff1bdp[0][j]\u540c\u7406<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int minDistance(string word1, string word2) {\n        \/\/\u4ee5\u4e0b\u6807i-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32word1,\u548c\u4ee5\u4e0b\u6807j-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32word2,\u6700\u8fd1\u7f16\u8f91\u8ddd\u79bb\u4e3adp&#91;i]&#91;j]\n        \/\/\u5373word1\u4e2d\u524di\u4e2a\u5b57\u6bcd\u7ec4\u6210\u7684\u5b57\u7b26\u4e32\uff0c\u548cword2\u4e2d\u524dj\u4e2a\u5b57\u6bcd\u7ec4\u6210\u7684\u5b57\u7b26\u4e32\uff0c\u6700\u8fd1\u7f16\u8f91\u8ddd\u79bb\u4e3adp&#91;i]&#91;j]\n        vector&lt;vector&lt;int&gt;&gt; dp(word1.size()+1, vector&lt;int&gt;(word2.size()+1, 0));\n        \/\/dp&#91;i]&#91;0]\uff1a\u4ee5\u4e0b\u6807i-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32word1,\u548c\u7a7a\u5b57\u7b26\u4e32word2,\u6700\u8fd1\u7f16\u8f91\u8ddd\u79bb\u4e3adp&#91;i]&#91;0],\u5373i \n        for(int i = 0; i &lt;= word1.size(); i++) dp&#91;i]&#91;0] = i;\n        for(int j = 0; j &lt;= word2.size(); j++) dp&#91;0]&#91;j] = j;\n\n        for(int i = 1; i &lt;= word1.size(); i++) {\n            for(int j = 1; j &lt;= word2.size(); j++) {\n                if(word1&#91;i-1] == word2&#91;j-1]) {\n                    dp&#91;i]&#91;j] = dp&#91;i-1]&#91;j-1];\n                } else {\n                    \/\/word1\u5220\u9664\u4e00\u4e2a\u5143\u7d20 or word2\u5220\u9664\u4e00\u4e2a\u5143\u7d20 or \u66ff\u6362\u4e00\u4e2a\u5143\u7d20\n                    dp&#91;i]&#91;j] = min({dp&#91;i-1]&#91;j], dp&#91;i]&#91;j-1], dp&#91;i-1]&#91;j-1]}) + 1;\n                }\n            }\n        }\n\n        return dp&#91;word1.size()]&#91;word2.size()];\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/maximum-length-of-repeated-subarray\/\"><\/a><a href=\"https:\/\/leetcode.cn\/problems\/distinct-subsequences\/\">115. \u4e0d\u540c\u7684\u5b50\u5e8f\u5217<\/a><\/h2>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/maximum-length-of-repeated-subarray\/\"><\/a><a href=\"https:\/\/leetcode.cn\/problems\/is-subsequence\/\">392. \u5224\u65ad\u5b50\u5e8f\u5217<\/a>\u2705<\/h2>\n\n\n\n<p><strong><em>Solution1\uff1a\u7b80\u5355<\/em><\/strong><em><strong>\u5faa\u73af\u5224\u65ad\uff08\u672c\u8d28\u53cc\u6307\u9488\uff09<\/strong><\/em><\/p>\n\n\n\n<p><strong><em>Solution2\uff1a\u770b\u6210\u7f16\u8f91\u8ddd\u79bb\u7684\u7b80\u5316\u7248\uff0c\u53ea\u9700\u8981\u8ba1\u7b97\u5220\u9664\u7684\u60c5\u51b5\uff0c\u4e0d\u7528\u8003\u8651\u589e\u52a0\u548c\u66ff\u6362<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>dp\u6570\u7ec4\u542b\u4e49\uff1a\u4ee5\u4e0b\u6807i-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32s\uff0c\u548c\u4ee5\u4e0b\u6807j-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32t\uff0c\u76f8\u540c\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\u4e3adp[i][j]<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution1 {\npublic:\n    bool isSubsequence(string s, string t) {\n        if(s.size() == 0) return true;\n        if(t.size() == 0) return false;\n        int k = 0;\n        for(int i = 0; i &lt; t.size(); i++) {\n            if(t&#91;i] == s&#91;k]) k++;\n            if(k == s.size()) return true;\n        }\n\n        return false;\n    }\n};<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution2 {\npublic:\n    bool isSubsequence(string s, string t) {\n        \/\/\u4ee5\u4e0b\u6807i-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32s\uff0c\u548c\u4ee5\u4e0b\u6807j-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32t\uff0c\u76f8\u540c\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\u4e3adp&#91;i]&#91;j]\n        vector&lt;vector&lt;int&gt;&gt; dp(s.size()+1, vector&lt;int&gt;(t.size()+1, 0));\n\n        for(int i = 1; i &lt;= s.size(); i++) {\n            for(int j = 1; j &lt;= t.size(); j++) {\n                if(s&#91;i-1] == t&#91;j-1]) dp&#91;i]&#91;j] = dp&#91;i-1]&#91;j-1] + 1;\n                else dp&#91;i]&#91;j] = dp&#91;i]&#91;j-1];\n            }\n        }\n\n        if(dp&#91;s.size()]&#91;t.size()] == s.size()) return true;\n        return false;\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/longest-continuous-increasing-subsequence\/\"><\/a><a href=\"https:\/\/leetcode.cn\/problems\/delete-operation-for-two-strings\/\">583. \u4e24\u4e2a\u5b57\u7b26\u4e32\u7684\u5220\u9664\u64cd\u4f5c<\/a><\/h2>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/maximum-length-of-repeated-subarray\/\"><\/a><a href=\"https:\/\/leetcode.cn\/problems\/longest-palindromic-subsequence\/\">516. \u6700\u957f\u56de\u6587\u5b50\u5e8f\u5217<\/a><\/h2>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/longest-continuous-increasing-subsequence\/\"><\/a><a href=\"https:\/\/leetcode.cn\/problems\/palindromic-substrings\/\">647. \u56de\u6587\u5b50\u4e32<\/a>\u274c<\/h2>\n\n\n\n<p><strong>Solution1\uff1aDP<\/strong><\/p>\n\n\n\n<p>dp\u6570\u7ec4\u542b\u4e49\uff1a\u8868\u793a\u533a\u95f4\u8303\u56f4[i,j]\u7684\u5b50\u4e32\u662f\u5426\u662f\u56de\u6587\u5b50\u4e32\uff0c\u5982\u679c\u662f\uff0c\u5219dp[i][j]\u4e3atrue\uff0c\u5426\u5219\u4e3afalse<\/p>\n\n\n\n<p>\u904d\u5386\u987a\u5e8f\uff1a\u4ece\u4e0b\u5230\u4e0a\uff0c\u4ece\u5de6\u5230\u53f3\uff08\u8be6\u89c1\u4ee3\u7801\u968f\u60f3\u5f55\uff09 <\/p>\n\n\n\n<p><strong>Solution2\uff1a\u53cc\u6307\u9488<\/strong><\/p>\n\n\n\n<p>\u904d\u5386\u4e2d\u5fc3\u70b9\u7684\uff0c\u6ce8\u610f\u4e2d\u5fc3\u70b9\u6709\u4e24\u79cd\u60c5\u51b5\uff1a\u4e00\u4e2a\u5143\u7d20\u53ef\u4ee5\u4f5c\u4e3a\u4e2d\u5fc3\u70b9\uff0c\u4e24\u4e2a\u5143\u7d20\u4e5f\u53ef\u4ee5\u4f5c\u4e3a\u4e2d\u5fc3\u70b9<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution1 {\npublic:\n    int countSubstrings(string s) {\n        vector&lt;vector&lt;bool&gt;&gt; dp(s.size() + 1, vector&lt;bool&gt;(s.size() + 1, false));\n        int cnt = 0;\n        for(int i = s.size() - 1; i &gt;= 0; i--) {\n            for(int j = i; j &lt; s.size(); j++) {\n                if(s&#91;i] == s&#91;j]) {\n                    if(j - i &lt;= 1) {\n                        dp&#91;i]&#91;j] = true;\n                        cnt++;\n                    } else if(dp&#91;i+1]&#91;j-1]){\n                        dp&#91;i]&#91;j] = true;\n                        cnt++;\n                    }\n                }\n            }\n        }\n\n        return cnt;\n    }\n};<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution2 {\nprivate:\n    int extend(string &amp;s, int l, int r) {\n        int num = 0;\n        while(l &gt;= 0 &amp;&amp; r &lt; s.size() &amp;&amp; s&#91;l] == s&#91;r]) {\n            num++;\n            l--;\n            r++;\n        }\n        return num;\n    }\npublic:\n    int countSubstrings(string s) {\n        int cnt = 0;\n        for(int i = 0; i &lt; s.size(); i++) {\n            cnt += extend(s, i, i);     \/\/\u4ee5\u4e00\u4e2a\u5143\u7d20\u4e3a\u4e2d\u5fc3\u70b9\n            cnt += extend(s, i, i + 1); \/\/\u4ee5\u4e24\u4e2a\u5143\u7d20\u4e3a\u4e2d\u5fc3\u70b9\n        }\n\n        return cnt;\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>More content\uff1aLeetCode hot100@\u52a8\u6001\u89c4\u5212&amp;\u591a\u7ef4\u52a8\u6001\u89c4\u5212 DP\u662f\u7531\u524d\u4e00\u4e2a\u72b6\u6001\u63a8 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[27,18,19,61],"class_list":["post-1746","post","type-post","status-publish","format-standard","hentry","category-suanfa","tag-c","tag-leetcode","tag-19","tag-61"],"_links":{"self":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/1746","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1746"}],"version-history":[{"count":74,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/1746\/revisions"}],"predecessor-version":[{"id":2328,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/1746\/revisions\/2328"}],"wp:attachment":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1746"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1746"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1746"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}