{"id":2449,"date":"2022-03-23T21:16:23","date_gmt":"2022-03-23T13:16:23","guid":{"rendered":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2449"},"modified":"2022-03-24T10:53:06","modified_gmt":"2022-03-24T02:53:06","slug":"dp","status":"publish","type":"post","link":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2449","title":{"rendered":"dp\u7b2c\u4e00\u5929"},"content":{"rendered":"\n

\u300c\u52a8\u6001\u89c4\u5212\u300d – \u5b66\u4e60\u8ba1\u5212 – \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

dp\u7b80\u5355\u9898\uff0c\u7b2c\u4e00\u9053\u6c38\u8fdc\u662f\u6590\u6ce2\u90a3\u5951\u6570\u5217<\/p>\n\n\n\n

509. \u6590\u6ce2\u90a3\u5951\u6570<\/a><\/p>\n\n\n\n

\/**
<\/em> \u6590\u6ce2\u90a3\u5951\u6570 \uff08\u901a\u5e38\u7528 F(n) \u8868\u793a\uff09\u5f62\u6210\u7684\u5e8f\u5217\u79f0\u4e3a \u6590\u6ce2\u90a3\u5951\u6570\u5217 \u3002\u8be5\u6570\u5217\u7531 0 \u548c 1 \u5f00\u59cb\uff0c\u540e\u9762\u7684\u6bcf\u4e00\u9879\u6570\u5b57\u90fd\u662f\u524d\u9762\u4e24\u9879\u6570\u5b57\u7684\u548c\u3002\u4e5f\u5c31\u662f\uff1a
<\/em>
<\/em> F(0) = 0\uff0cF(1) = 1
<\/em> F(n) = F(n - 1) + F(n - 2)\uff0c\u5176\u4e2d n > 1
<\/em> \u7ed9\u5b9a n \uff0c\u8bf7\u8ba1\u7b97 F(n) \u3002
<\/em>
<\/em>
<\/em>
<\/em> \u793a\u4f8b 1\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1an = 2
<\/em> \u8f93\u51fa\uff1a1
<\/em> \u89e3\u91ca\uff1aF(2) = F(1) + F(0) = 1 + 0 = 1
<\/em> \u793a\u4f8b 2\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1an = 3
<\/em> \u8f93\u51fa\uff1a2
<\/em> \u89e3\u91ca\uff1aF(3) = F(2) + F(1) = 1 + 1 = 2
<\/em> \u793a\u4f8b 3\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1an = 4
<\/em> \u8f93\u51fa\uff1a3
<\/em> \u89e3\u91ca\uff1aF(4) = F(3) + F(2) = 2 + 1 = 3
<\/em>
<\/em>
<\/em> \u63d0\u793a\uff1a
<\/em>
<\/em> 0 <= n <= 30
<\/em>
<\/em>
<\/em> \u6765\u6e90\uff1a\u529b\u6263\uff08LeetCode\uff09
<\/em> \u94fe\u63a5\uff1ahttps:\/\/leetcode-cn.com\/problems\/fibonacci-number
<\/em> \u8457\u4f5c\u6743\u5f52\u9886\u6263\u7f51\u7edc\u6240\u6709\u3002\u5546\u4e1a\u8f6c\u8f7d\u8bf7\u8054\u7cfb\u5b98\u65b9\u6388\u6743\uff0c\u975e\u5546\u4e1a\u8f6c\u8f7d\u8bf7\u6ce8\u660e\u51fa\u5904\u3002
<\/em>
<\/em> * <\/em>@author <\/em><\/strong>zeroheart
<\/em> *
<\/em> *\/
<\/em>public class Question509 {
    public int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 1;

        int[] r = new int[n+1];
        r[0] = 0;
        r[1] = 1;
        r[2] = 1;
        for(int i=3; i<=n; i++){
            r[i] = r[i-1] + r[i-2];
        }
        return r[n];
    }
}<\/pre>\n\n\n\n
\u8fd9\u4e2a\u9898\u76ee\u4e2d\u5df2\u7ecf\u628a\u8f6c\u79fb\u65b9\u7a0b\u5199\u51fa\u6765\u4e86\uff0c\u76f4\u63a5\u5d4c\u5957\u5c31\u884c\u3002F(n) = F(n – 1) + F(n – 2)<\/em><\/mark><\/p>\n\n\n\n
1137. \u7b2c N \u4e2a\u6cf0\u6ce2\u90a3\u5951\u6570<\/a><\/p>\n\n\n\n

\/**
<\/em> 1137. \u7b2c N \u4e2a\u6cf0\u6ce2\u90a3\u5951\u6570
<\/em> \u6cf0\u6ce2\u90a3\u5951\u5e8f\u5217 Tn \u5b9a\u4e49\u5982\u4e0b\uff1a
<\/em>
<\/em> T0 = 0, T1 = 1, T2 = 1, \u4e14\u5728 n >= 0 \u7684\u6761\u4ef6\u4e0b Tn+3 = Tn + Tn+1 + Tn+2
<\/em>
<\/em> \u7ed9\u4f60\u6574\u6570 n\uff0c\u8bf7\u8fd4\u56de\u7b2c n \u4e2a\u6cf0\u6ce2\u90a3\u5951\u6570 Tn \u7684\u503c\u3002
<\/em>
<\/em>
<\/em>
<\/em> \u793a\u4f8b 1\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1an = 4
<\/em> \u8f93\u51fa\uff1a4
<\/em> \u89e3\u91ca\uff1a
<\/em> T_3 = 0 + 1 + 1 = 2
<\/em> T_4 = 1 + 1 + 2 = 4
<\/em> \u793a\u4f8b 2\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1an = 25
<\/em> \u8f93\u51fa\uff1a1389537
<\/em>
<\/em>
<\/em> \u63d0\u793a\uff1a
<\/em>
<\/em> 0 <= n <= 37
<\/em> \u7b54\u6848\u4fdd\u8bc1\u662f\u4e00\u4e2a 32 \u4f4d\u6574\u6570\uff0c\u5373 answer <= 2^31 - 1\u3002
<\/em>
<\/em> * <\/em>@author <\/em><\/strong>zeroheart
<\/em> *
<\/em> *\/
<\/em>public class Question1137 {
    public int tribonacci(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 1;
        int[] r = new int[n+1];
        r[0] = 0;
        r[1] = 1;
        r[2] = 1;
        for(int i = 0; i <= n-3; i++){
            r[i+3] = r[i] + r[i+1] + r[i+2];
        }
        return r[n];
    }
}<\/pre>\n\n\n\n
\u672c\u9898\u4e5f\u662f\u6700\u7b80\u5355\u7684\u7c7b\u578b\uff0c\u516c\u5f0f\u5df2\u7ed9\u51faTn+3 = Tn + Tn+1 + Tn+2<\/em><\/mark><\/p>\n","protected":false},"excerpt":{"rendered":"
\u300c\u52a8\u6001\u89c4\u5212\u300d – \u5b66\u4e60\u8ba1\u5212 – \u529b\u6263\uff08LeetCode\uff09\u5168\u7403\u6781\u5ba2\u631a\u7231\u7684\u6280\u672f\u6210\u957f\u5e73\u53f0 ( […]<\/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,159,160],"_links":{"self":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2449"}],"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=2449"}],"version-history":[{"count":12,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2449\/revisions"}],"predecessor-version":[{"id":2477,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2449\/revisions\/2477"}],"wp:attachment":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2449"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2449"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2449"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}