{"id":85,"date":"2025-06-18T23:30:37","date_gmt":"2025-06-18T15:30:37","guid":{"rendered":"http:\/\/116.62.30.57\/?p=85"},"modified":"2025-06-18T23:30:39","modified_gmt":"2025-06-18T15:30:39","slug":"%e6%af%8f%e6%97%a5%e4%b8%80%e9%a2%98-%e4%b8%8d%e5%90%8c%e7%9a%84%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91","status":"publish","type":"post","link":"https:\/\/qiuqiqaq.fun\/index.php\/2025\/06\/18\/%e6%af%8f%e6%97%a5%e4%b8%80%e9%a2%98-%e4%b8%8d%e5%90%8c%e7%9a%84%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91\/","title":{"rendered":"\u6bcf\u65e5\u4e00\u9898\u2014\u2014\u4e0d\u540c\u7684\u4e8c\u53c9\u641c\u7d22\u6811"},"content":{"rendered":"\n

\u7ed9\u4f60\u4e00\u4e2a\u6574\u6570\u00a0n<\/code>\u00a0\uff0c\u6c42\u6070\u7531\u00a0n<\/code>\u00a0\u4e2a\u8282\u70b9\u7ec4\u6210\u4e14\u8282\u70b9\u503c\u4ece\u00a01<\/code>\u00a0\u5230\u00a0n<\/code>\u00a0\u4e92\u4e0d\u76f8\u540c\u7684\u00a0\u4e8c\u53c9\u641c\u7d22\u6811<\/strong>\u00a0\u6709\u591a\u5c11\u79cd\uff1f\u8fd4\u56de\u6ee1\u8db3\u9898\u610f\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u79cd\u6570\u3002<\/p>\n\n\n\n

\u793a\u4f8b 1\uff1a<\/strong><\/p>\n\n\n\n

\"\"\/<\/div><\/figure>\n\n\n\n
\u8f93\u5165\uff1a<\/strong>n = 3\n\u8f93\u51fa\uff1a<\/strong>5<\/pre>\n\n\n\n
\u793a\u4f8b 2\uff1a<\/strong>
\u8f93\u5165\uff1a<\/strong>n = 1
\u8f93\u51fa\uff1a<\/strong>1<\/pre>\n\n\n\n
\u63d0\u793a\uff1a<\/strong>
1 <= n <= 19<\/code><\/pre>\n\n\n\n
\u601d\u8def<\/h2>\n\n\n\n
\u7ed9\u5b9a\u4e00\u4e2a\u6709\u5e8f\u5e8f\u5217 1\u22efn\uff0c\u4e3a\u4e86\u6784\u5efa\u51fa\u4e00\u68f5\u4e8c\u53c9\u641c\u7d22\u6811\uff0c\u6211\u4eec\u53ef\u4ee5\u904d\u5386\u6bcf\u4e2a\u6570\u5b57 i\uff0c\u5c06\u8be5\u6570\u5b57\u4f5c\u4e3a\u6811\u6839\uff0c\u5c06 1\u22ef(i\u22121) \u5e8f\u5217\u4f5c\u4e3a\u5de6\u5b50\u6811\uff0c\u5c06 (i+1)\u22efn \u5e8f\u5217\u4f5c\u4e3a\u53f3\u5b50\u6811\u3002\u63a5\u7740\u6211\u4eec\u53ef\u4ee5\u6309\u7167\u540c\u6837\u7684\u65b9\u5f0f\u9012\u5f52\u6784\u5efa\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u3002<\/p>\n\n\n\n
\u5728\u4e0a\u8ff0\u6784\u5efa\u7684\u8fc7\u7a0b\u4e2d\uff0c\u7531\u4e8e\u6839\u7684\u503c\u4e0d\u540c\uff0c\u56e0\u6b64\u6211\u4eec\u80fd\u4fdd\u8bc1\u6bcf\u68f5\u4e8c\u53c9\u641c\u7d22\u6811\u662f\u552f\u4e00\u7684\u3002<\/p>\n\n\n\n
\u7531\u6b64\u53ef\u89c1\uff0c\u539f\u95ee\u9898\u53ef\u4ee5\u5206\u89e3\u6210\u89c4\u6a21\u8f83\u5c0f\u7684\u4e24\u4e2a\u5b50\u95ee\u9898\uff0c\u4e14\u5b50\u95ee\u9898\u7684\u89e3\u53ef\u4ee5\u590d\u7528\u3002\u56e0\u6b64\uff0c\u6211\u4eec\u53ef\u4ee5\u60f3\u5230\u4f7f\u7528\u52a8\u6001\u89c4\u5212\u6765\u6c42\u89e3\u672c\u9898\u3002\u52a8\u6001\u89c4\u5212\u4ecb\u7ecd\u70b9\u8fd9\u91cc<\/a><\/p>\n\n\n\n
\u5047\u8bbe n \u4e2a\u8282\u70b9\u5b58\u5728\u4e8c\u53c9\u6392\u5e8f\u6811\u7684\u4e2a\u6570\u662f G (n)\uff0c\u4ee4 f(i) \u4e3a\u4ee5 i \u4e3a\u6839\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u4e2a\u6570\uff0c\u5219
G(n)=f(1)+f(2)+f(3)+f(4)+\u2026+f(n)<\/p>\n\n\n\n
\u5f53 i \u4e3a\u6839\u8282\u70b9\u65f6\uff0c\u5176\u5de6\u5b50\u6811\u8282\u70b9\u4e2a\u6570\u4e3a i-1 \u4e2a\uff0c\u53f3\u5b50\u6811\u8282\u70b9\u4e3a n-i\uff0c\u5219
f(i)=G(i\u22121)\u2217G(n\u2212i)<\/p>\n\n\n\n
\u7efc\u5408\u4e24\u4e2a\u516c\u5f0f\u53ef\u4ee5\u5f97\u5230\u516c\u5f0f
G(n)=G(0)\u2217G(n\u22121)+G(1)\u2217(n\u22122)+\u2026+G(n\u22121)\u2217G(0)<\/p>\n\n\n\n
int numTrees(int n) {\n    int G[n+1];\n    memset(G, 0, sizeof(G));\n    G[0] = G[1] = 1;\n    \n    for(int i = 2; i < n+1; i++){\n        for(int j = 1; j <i+1; j++){\n            G[i] +=G[j-1]*G[i-j]; \n        }\n    }<\/code><\/pre>\n\n\n\n
\u590d\u6742\u5ea6\u5206\u6790<\/h2>\n\n\n\n
\u65f6\u95f4\u590d\u6742\u5ea6 : O(n2)\uff0c\u5176\u4e2d n \u8868\u793a\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u8282\u70b9\u4e2a\u6570\u3002G(n) \u51fd\u6570\u4e00\u5171\u6709 n \u4e2a\u503c\u9700\u8981\u6c42\u89e3\uff0c\u6bcf\u6b21\u6c42\u89e3\u9700\u8981 O(n) \u7684\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u56e0\u6b64\u603b\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a O(n2)\u3002<\/p>\n\n\n\n
\u7a7a\u95f4\u590d\u6742\u5ea6 : O(n)\u3002\u6211\u4eec\u9700\u8981 O(n) \u7684\u7a7a\u95f4\u5b58\u50a8 G \u6570\u7ec4\u3002<\/p>\n\n\n\n
\u53e6\u8f9f\u8e4a\u5f84<\/h2>\n\n\n\n
\u8fd9\u4e2a\u65f6\u5019\u5c31\u6709\u4eba\u4f1a\u8bf4\u4e86\uff0c\u4e3b\u64ad\u4e3b\u64ad\uff0c\u8fd9\u4e2a\u89e3\u6cd5\u8fd8\u662f\u592a\u8d39\u8111\u5b50\u4e86\uff0c\u590d\u6742\u5ea6\u8fd8\u9ad8\uff0c\u6709\u6ca1\u6709\u66f4\u52a0\u7b80\u5355\u53c8\u5f3a\u52bf\u7684\u89e3\u6cd5\u63a8\u8350\uff1f\u6709\u7684\u5144\u5f1f\u6709\u7684\u3002\u6211\u4eec\u6ce8\u610f\u5230<\/p>\n\n\n\n
1 <= n <= 19<\/code><\/pre>\n\n\n\n
\u4e8e\u662f\u4e4e\uff0c\u6211\u4eec\u62ff\u8d77\u8ba1\u7b97\u5668\u8fdb\u884c\u4e00\u70b9\u5c0f\u5c0f\u7684\u8fd0\u7b97\uff0c\u4fbf\u53ef\u4ee5\u5f97\u5230\u4e0b\u9762\u7684\u89e3\u6cd5<\/p>\n\n\n\n
int numTrees(int n) {\n    switch(n) \n        case 1: return 1;\n        case 2: return 2;\n        case 3: return 5;\n        case 4: return 14;\n        case 5: return 42;\n        case 6: return 132;\n        case 7: return 429;\n        case 8: return 1430;\n        case 9: return 4862;\n        case 10: return 16796;\n        case 11: return 58786;\n        case 12: return 208012;\n        case 13: return 742900;\n        case 14: return 2674440;\n        case 15: return 9694845;\n        case 16: return 35357670;\n        case 17: return 129644790;\n        case 18: return 477638700;\n        case 19: return 1767263190;\n        default: return 0;\n    }\n}<\/code><\/pre>\n\n\n\n
\u65f6\u95f4\u590d\u6742\u5ea6\u548c\u7a7a\u95f4\u590d\u6742\u5ea6\u90fd\u662fO(1)\u7684\u9876\u7ea7\u7b97\u6cd5\uff0c\u6700\u91cd\u8981\u7684\u662f\u4eba\u4eba\u90fd\u80fd\u770b\u61c2\uff01\uff01\uff01\u8fd9\u624d\u662f\u771f\u6b63\u7684\u7b97\u6cd5\uff01\uff01\uff01<\/p>\n","protected":false},"excerpt":{"rendered":"
\u7ed9\u4f60\u4e00\u4e2a\u6574\u6570\u00a0n\u00a0\uff0c\u6c42\u6070\u7531\u00a0n\u00a0\u4e2a\u8282\u70b9\u7ec4\u6210\u4e14\u8282\u70b9\u503c\u4ece\u00a01\u00a0\u5230\u00a0n\u00a0\u4e92\u4e0d\u76f8\u540c\u7684\u00a0\u4e8c\u53c9\u641c\u7d22\u6811\u00a0\u6709\u591a\u5c11\u79cd\uff1f\u8fd4\u56de\u6ee1\u8db3\u9898 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[14],"class_list":["post-85","post","type-post","status-publish","format-standard","hentry","category-leetcode","tag-14"],"_links":{"self":[{"href":"https:\/\/qiuqiqaq.fun\/index.php\/wp-json\/wp\/v2\/posts\/85","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/qiuqiqaq.fun\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/qiuqiqaq.fun\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/qiuqiqaq.fun\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/qiuqiqaq.fun\/index.php\/wp-json\/wp\/v2\/comments?post=85"}],"version-history":[{"count":5,"href":"https:\/\/qiuqiqaq.fun\/index.php\/wp-json\/wp\/v2\/posts\/85\/revisions"}],"predecessor-version":[{"id":90,"href":"https:\/\/qiuqiqaq.fun\/index.php\/wp-json\/wp\/v2\/posts\/85\/revisions\/90"}],"wp:attachment":[{"href":"https:\/\/qiuqiqaq.fun\/index.php\/wp-json\/wp\/v2\/media?parent=85"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/qiuqiqaq.fun\/index.php\/wp-json\/wp\/v2\/categories?post=85"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/qiuqiqaq.fun\/index.php\/wp-json\/wp\/v2\/tags?post=85"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}