{"id":2478,"date":"2022-03-24T16:38:41","date_gmt":"2022-03-24T08:38:41","guid":{"rendered":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2478"},"modified":"2022-03-24T16:38:41","modified_gmt":"2022-03-24T08:38:41","slug":"dp%e7%ac%ac%e4%ba%8c%e5%a4%a9","status":"publish","type":"post","link":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2478","title":{"rendered":"dp\u7b2c\u4e8c\u5929"},"content":{"rendered":"\n

\u300c\u52a8\u6001\u89c4\u5212\u300d \u2013 \u5b66\u4e60\u8ba1\u5212 \u2013 \u529b\u6263\uff08LeetCode\uff09\u5168\u7403\u6781\u5ba2\u631a\u7231\u7684\u6280\u672f\u6210\u957f\u5e73\u53f0 (leetcode-cn.com)<\/a><\/p>\n\n\n\n

70. \u722c\u697c\u68af<\/a><\/p>\n\n\n\n

\u8fd9\u4e00\u9898\u5c31\u6bd4\u6590\u6ce2\u90a3\u5951\u6570\u5217\u8981\u9ebb\u70e6\uff0c\u770b\u6211\u4e0b\u6211\u7684\u5907\u6ce8<\/p>\n\n\n\n

\/**\n 70. \u722c\u697c\u68af\n \u5047\u8bbe\u4f60\u6b63\u5728\u722c\u697c\u68af\u3002\u9700\u8981 n \u9636\u4f60\u624d\u80fd\u5230\u8fbe\u697c\u9876\u3002\n\n \u6bcf\u6b21\u4f60\u53ef\u4ee5\u722c 1 \u6216 2 \u4e2a\u53f0\u9636\u3002\u4f60\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u65b9\u6cd5\u53ef\u4ee5\u722c\u5230\u697c\u9876\u5462\uff1f\n\n \u793a\u4f8b 1\uff1a\n\n \u8f93\u5165\uff1an = 2\n \u8f93\u51fa\uff1a2\n \u89e3\u91ca\uff1a\u6709\u4e24\u79cd\u65b9\u6cd5\u53ef\u4ee5\u722c\u5230\u697c\u9876\u3002\n 1. 1 \u9636 + 1 \u9636\n 2. 2 \u9636\n \u793a\u4f8b 2\uff1a\n\n \u8f93\u5165\uff1an = 3\n \u8f93\u51fa\uff1a3\n \u89e3\u91ca\uff1a\u6709\u4e09\u79cd\u65b9\u6cd5\u53ef\u4ee5\u722c\u5230\u697c\u9876\u3002\n 1. 1 \u9636 + 1 \u9636 + 1 \u9636\n 2. 1 \u9636 + 2 \u9636\n 3. 2 \u9636 + 1 \u9636\n\n\n \u63d0\u793a\uff1a\n\n 1 <= n <= 45\n\n\n * <\/em>@author <\/em><\/strong>zeroheart\n *\n *\/\n<\/em>public class Question70 {\n\n    public int climbStairs(int n) {\n        \/**\n         *\n         1. f(n) = f(n-1) + 1 = f(n-2) + 2\n         2. f(n-1) = f(n-2) + 1\n         3. f(n) = 2f(n-2) + 3\n         \u4e0a\u9762\u662f\u6211\u4e00\u5f00\u59cb\u7684\u9519\u8bef\u63a8\u5bfc\uff0c\u8fd9\u4e2a\u770b\u4f3c\u5f88\u5408\u7406\uff0c\u5b9e\u9645\u4e0a\u6700\u7ec8f(n-1) = f(n-2) + 1\u8fd9\u4e2a\u4e0d\u80fd\u8fd9\u4e48\u5199\uff0cf(n-2)\u5982\u679c\u5f80\u524d\u8d70\u4e00\u6b65\uff0c\u5230\u4e86f(n-1)\uff0c\u90a3\u4e48\u8def\u5f84\u5c31\u56fa\u5b9a\u4e86.\n         \u6211\u4eec\u8981\u8ba8\u8bba\u7684\u662ff(n-2)\u7684\u65f6\u5019\u4e0d\u80fd\u8d70\u5230f(n-1)\uff0c\u5c31\u662f\u8bf4f(n-2)\u53ea\u80fd\u8d70\u4e24\u6b65\u76f4\u63a5\u5230f(n),f(n-1)\u8d70\u4e00\u6b65\u76f4\u63a5\u5230f(n)\uff0c\u8fd9\u6837\u5b50\uff0c\u95ee\u9898\u5c31\u53d8\u6210\u4e86\u5230f(n-1)\u548cf(n-2)\u7684\u65b9\u6cd5\uff0c\u5f97\u5230f(n)=f(n-1)+f(n-2)\n         \u6211\u4eec\u5bf9f(n)\u7684\u5b9a\u4e49\uff0c\u8981\u65f6\u523b\u8bb0\u5f97\uff0c\u8fd9\u91ccf(n)\u662f\u8d70\u5230n\u7684\u65b9\u6cd5\uff0c\u63a8\u5bfc\u6210\u4e3a\u8d70\u5230f(n-1)\u7684\u65b9\u6cd5+f(n-2)\u7684\u65b9\u6cd5\n         *\/<\/mark>\n        <\/em>if(n == 1) return 1;\n        if(n == 2) return 2;\n        if(n == 3) return 3;\n        int[] r = new int[n+1];\n        r[1] = 1;\n        r[2] = 2;\n        r[3] = 3;\n        for(int i = 4; i <= n; i++){\n            r[i] = r[i-1] + r[i-2];\n            \/\/ r[i] = 2 * r[i-2] + 3; \u9519\u8bef\u7684\u63a8\u5bfc\n        }\n        return r[n];\n    }\n\n}<\/pre>\n\n\n\n
746. \u4f7f\u7528\u6700\u5c0f\u82b1\u8d39\u722c\u697c\u68af<\/a><\/p>\n\n\n\n
\/**
<\/em> 746. \u4f7f\u7528\u6700\u5c0f\u82b1\u8d39\u722c\u697c\u68af
<\/em> \u7ed9\u4f60\u4e00\u4e2a\u6574\u6570\u6570\u7ec4 cost \uff0c\u5176\u4e2d cost[i] \u662f\u4ece\u697c\u68af\u7b2c i \u4e2a\u53f0\u9636\u5411\u4e0a\u722c\u9700\u8981\u652f\u4ed8\u7684\u8d39\u7528\u3002\u4e00\u65e6\u4f60\u652f\u4ed8\u6b64\u8d39\u7528\uff0c\u5373\u53ef\u9009\u62e9\u5411\u4e0a\u722c\u4e00\u4e2a\u6216\u8005\u4e24\u4e2a\u53f0\u9636\u3002
<\/em>
<\/em> \u4f60\u53ef\u4ee5\u9009\u62e9\u4ece\u4e0b\u6807\u4e3a 0 \u6216\u4e0b\u6807\u4e3a 1 \u7684\u53f0\u9636\u5f00\u59cb\u722c\u697c\u68af\u3002
<\/em>
<\/em> \u8bf7\u4f60\u8ba1\u7b97\u5e76\u8fd4\u56de\u8fbe\u5230\u697c\u68af\u9876\u90e8\u7684\u6700\u4f4e\u82b1\u8d39\u3002
<\/em>
<\/em>
<\/em>
<\/em> \u793a\u4f8b 1\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1acost = [10,15,20]
<\/em> \u8f93\u51fa\uff1a15
<\/em> \u89e3\u91ca\uff1a\u4f60\u5c06\u4ece\u4e0b\u6807\u4e3a 1 \u7684\u53f0\u9636\u5f00\u59cb\u3002
<\/em> - \u652f\u4ed8 15 \uff0c\u5411\u4e0a\u722c\u4e24\u4e2a\u53f0\u9636\uff0c\u5230\u8fbe\u697c\u68af\u9876\u90e8\u3002
<\/em> \u603b\u82b1\u8d39\u4e3a 15 \u3002
<\/em> \u793a\u4f8b 2\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1acost = [1,100,1,1,1,100,1,1,100,1]
<\/em> \u8f93\u51fa\uff1a6
<\/em> \u89e3\u91ca\uff1a\u4f60\u5c06\u4ece\u4e0b\u6807\u4e3a 0 \u7684\u53f0\u9636\u5f00\u59cb\u3002
<\/em> - \u652f\u4ed8 1 \uff0c\u5411\u4e0a\u722c\u4e24\u4e2a\u53f0\u9636\uff0c\u5230\u8fbe\u4e0b\u6807\u4e3a 2 \u7684\u53f0\u9636\u3002
<\/em> - \u652f\u4ed8 1 \uff0c\u5411\u4e0a\u722c\u4e24\u4e2a\u53f0\u9636\uff0c\u5230\u8fbe\u4e0b\u6807\u4e3a 4 \u7684\u53f0\u9636\u3002
<\/em> - \u652f\u4ed8 1 \uff0c\u5411\u4e0a\u722c\u4e24\u4e2a\u53f0\u9636\uff0c\u5230\u8fbe\u4e0b\u6807\u4e3a 6 \u7684\u53f0\u9636\u3002
<\/em> - \u652f\u4ed8 1 \uff0c\u5411\u4e0a\u722c\u4e00\u4e2a\u53f0\u9636\uff0c\u5230\u8fbe\u4e0b\u6807\u4e3a 7 \u7684\u53f0\u9636\u3002
<\/em> - \u652f\u4ed8 1 \uff0c\u5411\u4e0a\u722c\u4e24\u4e2a\u53f0\u9636\uff0c\u5230\u8fbe\u4e0b\u6807\u4e3a 9 \u7684\u53f0\u9636\u3002
<\/em> - \u652f\u4ed8 1 \uff0c\u5411\u4e0a\u722c\u4e00\u4e2a\u53f0\u9636\uff0c\u5230\u8fbe\u697c\u68af\u9876\u90e8\u3002
<\/em> \u603b\u82b1\u8d39\u4e3a 6 \u3002
<\/em>
<\/em>
<\/em> \u63d0\u793a\uff1a
<\/em>
<\/em> 2 <= cost.length <= 1000
<\/em> 0 <= cost[i] <= 999
<\/em>
<\/em> * <\/em>@author <\/em><\/strong>zeroheart
<\/em> *
<\/em> *\/
<\/em>public class Question746 {
    public int minCostClimbingStairs(int[] cost) {
        \/**
<\/em>         * dp[i] \u8868\u793a\u5230i\u7684\u6700\u5c0fcost
<\/em>         * \u53ef\u4ee5\u5f97\u5230\u516c\u5f0f
<\/em>         * dp[i] = min(dp[i-1] + cost[i-1] , dp[i-2] + cost[i-2])
<\/em>         *\/
<\/em>        <\/em>int[] dp = new int[cost.length+1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i <= cost.length; i++){
            dp[i] = Math.min<\/em>(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[cost.length];
    }
}<\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
\u300c\u52a8\u6001\u89c4\u5212\u300d \u2013 \u5b66\u4e60\u8ba1\u5212 \u2013 \u529b\u6263\uff08LeetCode\uff09\u5168\u7403\u6781\u5ba2\u631a\u7231\u7684\u6280\u672f\u6210\u957f\u5e73\u53f0 (leetcode-cn. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[155],"tags":[158,162],"_links":{"self":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2478"}],"collection":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2478"}],"version-history":[{"count":8,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2478\/revisions"}],"predecessor-version":[{"id":2486,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2478\/revisions\/2486"}],"wp:attachment":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2478"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2478"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2478"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}