{"id":2466,"date":"2022-01-29T12:10:14","date_gmt":"2022-01-29T04:10:14","guid":{"rendered":"http:\/\/139.9.1.231\/?p=2466"},"modified":"2022-01-29T12:12:58","modified_gmt":"2022-01-29T04:12:58","slug":"leetcodeday96","status":"publish","type":"post","link":"http:\/\/139.9.1.231\/index.php\/2022\/01\/29\/leetcodeday96\/","title":{"rendered":"leetcodeday96 &#8211;\u4e0d\u540c\u7684\u4e8c\u53c9\u641c\u7d22\u6811\uff08!\uff09"},"content":{"rendered":"\n<p>\u7ed9\u4f60\u4e00\u4e2a\u6574\u6570&nbsp;<code>n<\/code>&nbsp;\uff0c\u6c42\u6070\u7531&nbsp;<code>n<\/code>&nbsp;\u4e2a\u8282\u70b9\u7ec4\u6210\u4e14\u8282\u70b9\u503c\u4ece&nbsp;<code>1<\/code>&nbsp;\u5230&nbsp;<code>n<\/code>&nbsp;\u4e92\u4e0d\u76f8\u540c\u7684&nbsp;<strong>\u4e8c\u53c9\u641c\u7d22\u6811<\/strong>&nbsp;\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<p><strong>\u793a\u4f8b 1\uff1a<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image is-style-default\"><img src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/01\/18\/uniquebstn3.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-code\"><code><strong>\u8f93\u5165\uff1a<\/strong>n = 3\n<strong>\u8f93\u51fa\uff1a<\/strong>5<\/code><\/pre>\n\n\n\n<p><strong>\u793a\u4f8b 2\uff1a<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><strong>\u8f93\u5165\uff1a<\/strong>n = 1\n<strong>\u8f93\u51fa\uff1a<\/strong>1<\/code><\/pre>\n\n\n\n<p><strong>\u63d0\u793a\uff1a<\/strong><\/p>\n\n\n\n<ul><li><code>1 &lt;= n &lt;= 19<\/code><\/li><\/ul>\n\n\n\n<p class=\"has-light-pink-background-color has-background\">\u601d\u8def\uff1a\u52a8\u6001\u89c4\u5212\u65b9\u6cd5\uff1a\uff08\u9700\u8981\u4ed4\u7ec6\u89c2\u5bdf\uff0c\u52a8\u624b\u7ed8\u753b\u624d\u80fd\u53d1\u73b0dp\u4e4b\u95f4\u7684\u89c4\u5f8b\uff09<\/p>\n\n\n\n<p>dp[3]\uff0c\u5c31\u662f \u5143\u7d201\u4e3a\u5934\u7ed3\u70b9\u641c\u7d22\u6811\u7684\u6570\u91cf + \u5143\u7d202\u4e3a\u5934\u7ed3\u70b9\u641c\u7d22\u6811\u7684\u6570\u91cf + \u5143\u7d203\u4e3a\u5934\u7ed3\u70b9\u641c\u7d22\u6811\u7684\u6570\u91cf<\/p>\n\n\n\n<p>\u5143\u7d201\u4e3a\u5934\u7ed3\u70b9\u641c\u7d22\u6811\u7684\u6570\u91cf = \u53f3\u5b50\u6811\u67092\u4e2a\u5143\u7d20\u7684\u641c\u7d22\u6811\u6570\u91cf * \u5de6\u5b50\u6811\u67090\u4e2a\u5143\u7d20\u7684\u641c\u7d22\u6811\u6570\u91cf<\/p>\n\n\n\n<p>\u5143\u7d202\u4e3a\u5934\u7ed3\u70b9\u641c\u7d22\u6811\u7684\u6570\u91cf = \u53f3\u5b50\u6811\u67091\u4e2a\u5143\u7d20\u7684\u641c\u7d22\u6811\u6570\u91cf * \u5de6\u5b50\u6811\u67091\u4e2a\u5143\u7d20\u7684\u641c\u7d22\u6811\u6570\u91cf<\/p>\n\n\n\n<p>\u5143\u7d203\u4e3a\u5934\u7ed3\u70b9\u641c\u7d22\u6811\u7684\u6570\u91cf = \u53f3\u5b50\u6811\u67090\u4e2a\u5143\u7d20\u7684\u641c\u7d22\u6811\u6570\u91cf * \u5de6\u5b50\u6811\u67092\u4e2a\u5143\u7d20\u7684\u641c\u7d22\u6811\u6570\u91cf<\/p>\n\n\n\n<p>\u67092\u4e2a\u5143\u7d20\u7684\u641c\u7d22\u6811\u6570\u91cf\u5c31\u662fdp[2]\u3002<\/p>\n\n\n\n<p>\u67091\u4e2a\u5143\u7d20\u7684\u641c\u7d22\u6811\u6570\u91cf\u5c31\u662fdp[1]\u3002<\/p>\n\n\n\n<p>\u67090\u4e2a\u5143\u7d20\u7684\u641c\u7d22\u6811\u6570\u91cf\u5c31\u662fdp[0]\u3002<\/p>\n\n\n\n<p>\u6240\u4ee5dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]<\/p>\n\n\n\n<ol><li>\u786e\u5b9adp\u6570\u7ec4\uff08dp table\uff09\u4ee5\u53ca\u4e0b\u6807\u7684\u542b\u4e49<\/li><\/ol>\n\n\n\n<p><strong>dp[i] \uff1a 1\u5230i\u4e3a\u8282\u70b9\u7ec4\u6210\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u4e2a\u6570\u4e3adp[i]<\/strong>\u3002<\/p>\n\n\n\n<p>\u4e5f\u53ef\u4ee5\u7406\u89e3\u662fi\u7684\u4e0d\u540c\u5143\u7d20\u8282\u70b9\u7ec4\u6210\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u4e2a\u6570\u4e3adp[i] \uff0c\u90fd\u662f\u4e00\u6837\u7684\u3002<\/p>\n\n\n\n<p>\u4ee5\u4e0b\u5206\u6790\u5982\u679c\u60f3\u4e0d\u6e05\u695a\uff0c\u5c31\u6765\u56de\u60f3\u4e00\u4e0bdp[i]\u7684\u5b9a\u4e49<\/p>\n\n\n\n<ol start=\"2\"><li>\u786e\u5b9a\u9012\u63a8\u516c\u5f0f<\/li><\/ol>\n\n\n\n<p>\u5728\u4e0a\u9762\u7684\u5206\u6790\u4e2d\uff0c\u5176\u5b9e\u5df2\u7ecf\u770b\u51fa\u5176\u9012\u63a8\u5173\u7cfb\uff0c dp[i] += dp[\u4ee5j\u4e3a\u5934\u7ed3\u70b9\u5de6\u5b50\u6811\u8282\u70b9\u6570\u91cf] * dp[\u4ee5j\u4e3a\u5934\u7ed3\u70b9\u53f3\u5b50\u6811\u8282\u70b9\u6570\u91cf]<\/p>\n\n\n\n<p>j\u76f8\u5f53\u4e8e\u662f\u5934\u7ed3\u70b9\u7684\u5143\u7d20\uff0c\u4ece1\u904d\u5386\u5230i\u4e3a\u6b62\u3002<\/p>\n\n\n\n<p>\u6240\u4ee5\u9012\u63a8\u516c\u5f0f\uff1adp[i] += dp[j &#8211; 1] * dp[i &#8211; j]; \uff0cj-1 \u4e3aj\u4e3a\u5934\u7ed3\u70b9\u5de6\u5b50\u6811\u8282\u70b9\u6570\u91cf\uff0ci-j \u4e3a\u4ee5j\u4e3a\u5934\u7ed3\u70b9\u53f3\u5b50\u6811\u8282\u70b9\u6570\u91cf<\/p>\n\n\n\n<ol start=\"3\"><li>dp\u6570\u7ec4\u5982\u4f55\u521d\u59cb\u5316<\/li><\/ol>\n\n\n\n<p>\u521d\u59cb\u5316\uff0c\u53ea\u9700\u8981\u521d\u59cb\u5316dp[0]\u5c31\u53ef\u4ee5\u4e86\uff0c\u63a8\u5bfc\u7684\u57fa\u7840\uff0c\u90fd\u662fdp[0]\u3002<\/p>\n\n\n\n<p>\u90a3\u4e48dp[0]\u5e94\u8be5\u662f\u591a\u5c11\u5462\uff1f<\/p>\n\n\n\n<p>\u4ece\u5b9a\u4e49\u4e0a\u6765\u8bb2\uff0c\u7a7a\u8282\u70b9\u4e5f\u662f\u4e00\u68f5\u4e8c\u53c9\u6811\uff0c\u4e5f\u662f\u4e00\u68f5\u4e8c\u53c9\u641c\u7d22\u6811\uff0c\u8fd9\u662f\u53ef\u4ee5\u8bf4\u5f97\u901a\u7684\u3002<\/p>\n\n\n\n<p>\u4ece\u9012\u5f52\u516c\u5f0f\u4e0a\u6765\u8bb2\uff0cdp[\u4ee5j\u4e3a\u5934\u7ed3\u70b9\u5de6\u5b50\u6811\u8282\u70b9\u6570\u91cf] * dp[\u4ee5j\u4e3a\u5934\u7ed3\u70b9\u53f3\u5b50\u6811\u8282\u70b9\u6570\u91cf] \u4e2d\u4ee5j\u4e3a\u5934\u7ed3\u70b9\u5de6\u5b50\u6811\u8282\u70b9\u6570\u91cf\u4e3a0\uff0c\u4e5f\u9700\u8981dp[\u4ee5j\u4e3a\u5934\u7ed3\u70b9\u5de6\u5b50\u6811\u8282\u70b9\u6570\u91cf] = 1\uff0c \u5426\u5219\u4e58\u6cd5\u7684\u7ed3\u679c\u5c31\u90fd\u53d8\u62100\u4e86\u3002<\/p>\n\n\n\n<p>\u6240\u4ee5\u521d\u59cb\u5316dp[0] = 1<\/p>\n\n\n\n<ol start=\"4\"><li>\u786e\u5b9a\u904d\u5386\u987a\u5e8f<\/li><\/ol>\n\n\n\n<p>\u9996\u5148\u4e00\u5b9a\u662f\u904d\u5386\u8282\u70b9\u6570\uff0c\u4ece\u9012\u5f52\u516c\u5f0f\uff1adp[i] += dp[j &#8211; 1] * dp[i &#8211; j]\u53ef\u4ee5\u770b\u51fa\uff0c\u8282\u70b9\u6570\u4e3ai\u7684\u72b6\u6001\u662f\u4f9d\u9760 i\u4e4b\u524d\u8282\u70b9\u6570\u7684\u72b6\u6001\u3002<\/p>\n\n\n\n<p>\u90a3\u4e48\u904d\u5386i\u91cc\u9762\u6bcf\u4e00\u4e2a\u6570\u4f5c\u4e3a\u5934\u7ed3\u70b9\u7684\u72b6\u6001\uff0c\u7528j\u6765\u904d\u5386\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#\n# @lc app=leetcode.cn id=96 lang=python3\n#\n# &#91;96] \u4e0d\u540c\u7684\u4e8c\u53c9\u641c\u7d22\u6811\n#\n\n# @lc code=start\nclass Solution:\n    def numTrees(self, n: int) -&gt; int:\n        dp=&#91;0]*(n+1)\n        dp&#91;0]=1\n        for i in range(1,n+1):\n            for j in range(1,i+1):\n                dp&#91;i] += dp&#91;j - 1] * dp&#91;i - j]\n        return dp&#91;n]\n# @lc code=end<\/code><\/pre>\n\n\n\n<div class=\"wp-block-image is-style-default\"><figure class=\"aligncenter size-full is-resized\"><img loading=\"lazy\" src=\"http:\/\/139.9.1.231\/wp-content\/uploads\/2022\/01\/image-307.png\" alt=\"\" class=\"wp-image-2471\" width=\"464\" height=\"120\" srcset=\"http:\/\/139.9.1.231\/wp-content\/uploads\/2022\/01\/image-307.png 883w, http:\/\/139.9.1.231\/wp-content\/uploads\/2022\/01\/image-307-300x78.png 300w, http:\/\/139.9.1.231\/wp-content\/uploads\/2022\/01\/image-307-768x199.png 768w\" sizes=\"(max-width: 464px) 100vw, 464px\" \/><\/figure><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u7ed9\u4f60\u4e00\u4e2a\u6574\u6570&nbsp;n&nbsp;\uff0c\u6c42\u6070\u7531&nbsp;n&nbsp;\u4e2a\u8282\u70b9\u7ec4\u6210\u4e14\u8282\u70b9\u503c\u4ece&nbsp;1&#038;n &hellip; <a href=\"http:\/\/139.9.1.231\/index.php\/2022\/01\/29\/leetcodeday96\/\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">leetcodeday96 &#8211;\u4e0d\u540c\u7684\u4e8c\u53c9\u641c\u7d22\u6811\uff08!\uff09<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[6],"tags":[],"_links":{"self":[{"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/posts\/2466"}],"collection":[{"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/comments?post=2466"}],"version-history":[{"count":5,"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/posts\/2466\/revisions"}],"predecessor-version":[{"id":2473,"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/posts\/2466\/revisions\/2473"}],"wp:attachment":[{"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/media?parent=2466"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/categories?post=2466"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/tags?post=2466"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}