{"id":1707,"date":"2026-06-02T16:59:02","date_gmt":"2026-06-02T08:59:02","guid":{"rendered":"http:\/\/wordpress.fangt.online\/?p=1707"},"modified":"2026-06-02T16:59:02","modified_gmt":"2026-06-02T08:59:02","slug":"%e9%80%92%e5%bd%92%e5%87%bd%e6%95%b0%e6%b7%b1%e5%85%a5","status":"publish","type":"post","link":"http:\/\/wordpress.fangt.online\/index.php\/2026\/06\/02\/%e9%80%92%e5%bd%92%e5%87%bd%e6%95%b0%e6%b7%b1%e5%85%a5\/","title":{"rendered":"\u9012\u5f52\u51fd\u6570\u6df1\u5165"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">\u8bb0\u5fc6\u5316\u4f18\u5316\uff08Memoization\uff09<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u95ee\u9898\u80cc\u666f<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u6734\u7d20\u9012\u5f52\u5f80\u5f80\u5b58\u5728<strong>\u91cd\u53e0\u5b50\u95ee\u9898<\/strong>\uff08Overlapping Subproblems\uff09\uff0c\u5bfc\u81f4\u540c\u4e00\u72b6\u6001\u88ab\u91cd\u590d\u8ba1\u7b97\u3002\u4ee5\u8ba1\u7b97\u6590\u6ce2\u90a3\u5951\u6570\u5217 <code>fib(n)<\/code> \u4e3a\u4f8b\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int fib(int n) {\n    if (n &lt; 2) return n;\n    return fib(n - 1) + fib(n - 2);\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u8c03\u7528 <code>fib(5)<\/code> \u65f6\uff0c<code>fib(3)<\/code> \u88ab\u8ba1\u7b97 2 \u6b21\uff0c<code>fib(2)<\/code> \u88ab\u8ba1\u7b97 3 \u6b21\u3002\u5f53 n=40 \u65f6\uff0c\u91cd\u590d\u8ba1\u7b97\u91cf\u5448\u6307\u6570\u7206\u70b8\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u8bb0\u5fc6\u5316\u7684\u6838\u5fc3\u601d\u60f3<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u7528\u7a7a\u95f4\u6362\u65f6\u95f4<\/strong>\uff1a\u5c06\u5df2\u7ecf\u8ba1\u7b97\u8fc7\u7684\u7ed3\u679c\u5b58\u50a8\u8d77\u6765\uff0c\u5f53\u518d\u6b21\u9047\u5230\u76f8\u540c\u8f93\u5165\u65f6\u76f4\u63a5\u8fd4\u56de\u7f13\u5b58\u7ed3\u679c\uff0c\u907f\u514d\u91cd\u590d\u8ba1\u7b97\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8bb0\u5fc6\u5316\u901a\u5e38\u914d\u5408\u9012\u5f52\u4f7f\u7528\uff0c\u5c5e\u4e8e<strong>\u81ea\u9876\u5411\u4e0b\u52a8\u6001\u89c4\u5212<\/strong>\uff08Top\u2011Down DP\uff09\u7684\u4e00\u79cd\u5b9e\u73b0\u65b9\u5f0f\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u5b9e\u73b0\u65b9\u6cd5<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728 C++ \u4e2d\u5e38\u7528\u6570\u7ec4\u4f5c\u4e3a\u7f13\u5b58\u5bb9\u5668\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u793a\u4f8b\uff1a\u8bb0\u5fc6\u5316\u6590\u6ce2\u90a3\u5951<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream&gt;\n#include &lt;vector&gt;\nusing namespace std;\n\nlong long memo&#91;1000005] = {0, 1};\nlong long fib(int n) {\n    if (n &lt; 0) return -1;\n    if (n == 0 || n == 1) return n;         \n    if (memo&#91;n] != 0) return memo&#91;n];      \n    memo&#91;n] = fib(n - 1) + fib(n - 2);\n    return memo&#91;n];\n}\n\nint main() {\n    cout &lt;&lt; fib(50) &lt;&lt; endl;   \/\/ \u77ac\u95f4\u5f97\u51fa\u7ed3\u679c\uff0c\u65e0\u91cd\u590d\u8ba1\u7b97\n    return 0;\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u65f6\u95f4\u590d\u6742\u5ea6<\/strong>\uff1aO(n) \uff08\u6bcf\u4e2a\u72b6\u6001\u53ea\u8ba1\u7b97\u4e00\u6b21\uff09<br><strong>\u7a7a\u95f4\u590d\u6742\u5ea6<\/strong>\uff1aO(n) \uff08\u9012\u5f52\u6808\u6df1\u5ea6 + \u7f13\u5b58\u6570\u7ec4\uff09<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u4ec0\u4e48\u65f6\u5019\u4f7f\u7528\u8bb0\u5fc6\u5316<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u2705 \u95ee\u9898\u5177\u6709<strong>\u91cd\u53e0\u5b50\u95ee\u9898<\/strong>\uff08\u5982\u6590\u6ce2\u90a3\u5951\u3001\u722c\u697c\u68af\u3001\u80cc\u5305\u3001\u533a\u95f4DP\uff09<\/li>\n\n\n\n<li>\u2705 \u9012\u5f52\u6811\u4e2d\u5b58\u5728\u5927\u91cf\u91cd\u590d\u8282\u70b9<\/li>\n\n\n\n<li>\u2705 \u72b6\u6001\u7a7a\u95f4\u6709\u9650\uff0c\u53ef\u88ab\u7f13\u5b58<\/li>\n\n\n\n<li>\u274c \u6bcf\u4e2a\u5b50\u95ee\u9898\u53ea\u51fa\u73b0\u4e00\u6b21\uff08\u5982\u6c49\u8bfa\u5854\u3001\u4e8c\u53c9\u6811\u904d\u5386\uff09\u2192 \u8bb0\u5fc6\u5316\u65e0\u6536\u76ca<\/li>\n\n\n\n<li>\u274c \u72b6\u6001\u7a7a\u95f4\u8fc7\u5927\uff08\u5982\u5168\u6392\u5217\u7684\u6307\u6570\u7ea7\u72b6\u6001\uff09\u2192 \u7f13\u5b58\u4e0d\u53ef\u884c<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u5e38\u89c1\u9012\u5f52\u9898\u578b<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u6c49\u8bfa\u5854\uff08Tower of Hanoi\uff09<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u95ee\u9898\u63cf\u8ff0<\/strong>\uff1a\u4e09\u6839\u67f1\u5b50 A\uff08\u6e90\uff09\u3001B\uff08\u8f85\u52a9\uff09\u3001C\uff08\u76ee\u6807\uff09\uff0c\u5c06 A \u4e0a\u7684 n \u4e2a\u5706\u76d8\uff08\u5927\u5c0f\u4e0d\u540c\uff09\u5168\u90e8\u79fb\u52a8\u5230 C\uff0c\u89c4\u5219\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u6bcf\u6b21\u79fb\u52a8\u4e00\u4e2a\u5706\u76d8<\/li>\n\n\n\n<li>\u5927\u76d8\u4e0d\u80fd\u538b\u5728\u5c0f\u76d8\u4e0a<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u9012\u5f52\u601d\u8def<\/strong>\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u5c06\u4e0a\u9762 n-1 \u4e2a\u5706\u76d8\u4ece A \u79fb\u5230 B\uff08\u501f\u52a9 C\uff09<\/li>\n\n\n\n<li>\u5c06\u7b2c n \u4e2a\u5706\u76d8\u4ece A \u76f4\u63a5\u79fb\u5230 C<\/li>\n\n\n\n<li>\u5c06 B \u4e0a\u7684 n-1 \u4e2a\u5706\u76d8\u79fb\u5230 C\uff08\u501f\u52a9 A\uff09<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u4ee3\u7801<\/strong>\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream&gt;\nusing namespace std;\n\nvoid hanoi(int n, char from, char to, char aux) {\n    if (n == 1) {\n        cout &lt;&lt; n &lt;&lt; \" from \" &lt;&lt; from &lt;&lt; \" to \" &lt;&lt; to &lt;&lt; endl;\n        return;\n    }\n    hanoi(n - 1, from, aux, to);\n    cout &lt;&lt; n &lt;&lt; \" from \" &lt;&lt; from &lt;&lt; \" to \" &lt;&lt; to &lt;&lt; endl;\n    hanoi(n - 1, aux, to, from);\n}\n\nint main() {\n    hanoi(3, 'A', 'C', 'B');\n    return 0;\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u65f6\u95f4\u590d\u6742\u5ea6<\/strong>\uff1aO(2\u207f) \uff08\u79fb\u52a8\u6b21\u6570\u6070\u597d\u4e3a 2\u207f &#8211; 1\uff09<br><strong>\u662f\u5426\u53ef\u8bb0\u5fc6\u5316<\/strong>\uff1a\u274c \u6bcf\u4e2a\u5b50\u95ee\u9898\u72b6\u6001 <code>(n, from, to, aux)<\/code> \u7ec4\u5408\u4e0d\u540c\uff0c\u65e0\u91cd\u53e0\u5b50\u95ee\u9898\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u722c\u697c\u68af\uff08Climbing Stairs\uff09<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u95ee\u9898<\/strong>\uff1a\u4e00\u6b21\u53ef\u4ee5\u722c 1 \u9636\u6216 2 \u9636\u697c\u68af\uff0c\u6c42\u722c\u5230\u7b2c n \u9636\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u65b9\u6cd5\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u9012\u5f52\u5173\u7cfb<\/strong>\uff1a<code>ways(n) = ways(n-1) + ways(n-2)<\/code>\uff0c\u8fb9\u754c <code>ways(1)=1, ways(2)=2<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u6734\u7d20\u9012\u5f52\uff08\u91cd\u53e0\u5b50\u95ee\u9898\u4e25\u91cd\uff09<\/strong>\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int climbStairs(int n) {\n    if (n == 1) return 1;\n    if (n == 2) return 2;\n    return climbStairs(n - 1) + climbStairs(n - 2);\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u8bb0\u5fc6\u5316\u4f18\u5316<\/strong>\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int memo&#91;1000005] = {1, 1, 2};\nint climbStairs(int n) {\n    if (n == 1) return 1;\n    if (n == 2) return 2;\n    if (memo&#91;n] != 0) return memo&#91;n];\n    memo&#91;n] = climbStairs(n - 1) + climbStairs(n - 2);\n    return memo&#91;n];\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u8fdb\u9636\u53d8\u79cd<\/strong>\uff1a\u4e00\u6b21\u53ef\u4ee5\u722c 1\u30012\u30013 \u9636 \u2192 \u9012\u63a8\u5f0f\u53d8\u4e3a <code>ways(n) = ways(n-1)+ways(n-2)+ways(n-3)<\/code><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u5168\u6392\u5217\uff08Permutations\uff09<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u95ee\u9898<\/strong>\uff1a\u7ed9\u5b9a\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u8fd4\u56de\u6240\u6709\u53ef\u80fd\u7684\u5168\u6392\u5217\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u9012\u5f52\u601d\u8def<\/strong>\uff1a\u56de\u6eaf\u6cd5\uff0c\u4f9d\u6b21\u786e\u5b9a\u6bcf\u4e2a\u4f4d\u7f6e\u7684\u5143\u7d20\uff0c\u4f7f\u7528 <code>used<\/code> \u6570\u7ec4\u6807\u8bb0\u5df2\u9009\u5143\u7d20\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u4ee3\u7801<\/strong>\uff08\u65e0\u9700\u8bb0\u5fc6\u5316\uff0c\u56e0\u4e3a\u6bcf\u4e2a\u6392\u5217\u90fd\u662f\u65b0\u72b6\u6001\uff09\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream>\n#include &lt;string>\n#include &lt;cstring>\nusing namespace std;\n\nstring s;          \/\/ \u539f\u59cb\u5b57\u7b26\u4e32\uff08\u5168\u5c40\uff09\nbool used&#91;100];    \/\/ \u6807\u8bb0\u5b57\u7b26\u662f\u5426\u7528\u8fc7\uff08\u5168\u5c40\uff09\nchar cur&#91;100];     \/\/ \u5f53\u524d\u6392\u5217\uff08\u5168\u5c40\uff09\nint n;             \/\/ \u5b57\u7b26\u4e32\u957f\u5ea6\uff08\u5168\u5c40\uff09\n\n\/\/ \u6df1\u5ea6\u4f18\u5148\u641c\u7d22\uff0cdepth\u8868\u793a\u5f53\u524d\u5df2\u7ecf\u9009\u4e86\u51e0\u4e2a\u5b57\u7b26\nvoid dfs(int depth) {\n    if (depth == n) {\n        cur&#91;depth] = '\\0';      \/\/ \u52a0\u4e0a\u5b57\u7b26\u4e32\u7ed3\u675f\u7b26\n        cout &lt;&lt; cur &lt;&lt; endl;    \/\/ \u8f93\u51fa\u4e00\u4e2a\u6392\u5217\n        return;\n    }\n    for (int i = 0; i &lt; n; ++i) {\n        if (!used&#91;i]) {\n            used&#91;i] = true;\n            cur&#91;depth] = s&#91;i];  \/\/ \u9009\u62e9\u7b2ci\u4e2a\u5b57\u7b26\n            dfs(depth + 1);     \/\/ \u9012\u5f52\u4e0b\u4e00\u5c42\n            used&#91;i] = false;    \/\/ \u56de\u6eaf\uff0c\u64a4\u9500\u9009\u62e9\n        }\n    }\n}\n\nint main() {\n    cin >> s;          \/\/ \u8f93\u5165\u5b57\u7b26\u4e32\uff0c\u4f8b\u5982 \"abc\"\n    n = s.length();\n    dfs(0);\n    return 0;\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>C++\u81ea\u5e26\u5168\u6392\u5217\u51fd\u6570<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong><code>std::next_permutation(begin, end)<\/code><\/strong><br>\u5c06\u5f53\u524d\u5e8f\u5217\u53d8\u4e3a<strong>\u5b57\u5178\u5e8f\u4e0b\u4e00\u4e2a<\/strong>\u66f4\u5927\u7684\u6392\u5217\u3002\u5982\u679c\u5b58\u5728\u4e0b\u4e00\u4e2a\u6392\u5217\uff0c\u8fd4\u56de\u00a0<code>true<\/code>\uff1b\u82e5\u5df2\u662f\u6700\u540e\u4e00\u4e2a\u6392\u5217\uff08\u5373\u964d\u5e8f\uff09\uff0c\u5219\u53d8\u4e3a\u7b2c\u4e00\u4e2a\u6392\u5217\uff08\u5347\u5e8f\uff09\u5e76\u8fd4\u56de\u00a0<code>false<\/code>\u3002<\/li>\n\n\n\n<li><strong><code>std::prev_permutation(begin, end)<\/code><\/strong><br>\u53d8\u4e3a\u5b57\u5178\u5e8f\u4e0a\u4e00\u4e2a\u66f4\u5c0f\u7684\u6392\u5217\u3002<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream>\n#include &lt;algorithm>   \/\/ next_permutation\n#include &lt;string>\nusing namespace std;\n\nint main() {\n    string s = \"abc\";\n    \/\/ \u7b2c\u4e00\u6b65\uff1a\u5fc5\u987b\u5148\u6392\u5e8f\uff0c\u4fdd\u8bc1\u4ece\u7b2c\u4e00\u4e2a\u6392\u5217\u5f00\u59cb\n    sort(s.begin(), s.end());\n    \n    do {\n        cout &lt;&lt; s &lt;&lt; endl;   \/\/ \u8f93\u51fa\u5f53\u524d\u6392\u5217\n    } while (next_permutation(s.begin(), s.end()));\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>int arr&#91;] = {1, 2, 3};\nint n = sizeof(arr) \/ sizeof(arr&#91;0]);\nsort(arr, arr + n);\ndo {\n    for (int x : arr) cout &lt;&lt; x &lt;&lt; \" \";\n    cout &lt;&lt; endl;\n} while (next_permutation(arr, arr + n));<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u8bb0\u5fc6\u5316\u4f18\u5316\uff08Memoization\uff09 \u95ee\u9898\u80cc\u666f \u6734\u7d20\u9012\u5f52\u5f80\u5f80\u5b58\u5728\u91cd\u53e0\u5b50\u95ee\u9898\uff08Overlapping Subpr [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[61],"tags":[],"class_list":["post-1707","post","type-post","status-publish","format-standard","hentry","category-zl"],"_links":{"self":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/1707","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/comments?post=1707"}],"version-history":[{"count":3,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/1707\/revisions"}],"predecessor-version":[{"id":1714,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/1707\/revisions\/1714"}],"wp:attachment":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/media?parent=1707"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/categories?post=1707"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/tags?post=1707"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}