{"id":2661,"date":"2022-04-08T23:01:25","date_gmt":"2022-04-08T15:01:25","guid":{"rendered":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2661"},"modified":"2022-04-08T23:01:38","modified_gmt":"2022-04-08T15:01:38","slug":"dp%e7%ac%ac11%e5%a4%a9","status":"publish","type":"post","link":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2661","title":{"rendered":"dp\u7b2c11\u5929"},"content":{"rendered":"\n

264. \u4e11\u6570 II<\/a><\/p>\n\n\n\n


\/**
<\/em> 264. \u4e11\u6570 II
<\/em> \u7ed9\u4f60\u4e00\u4e2a\u6574\u6570 n \uff0c\u8bf7\u4f60\u627e\u51fa\u5e76\u8fd4\u56de\u7b2c n \u4e2a \u4e11\u6570 \u3002
<\/em>
<\/em> \u4e11\u6570 \u5c31\u662f\u53ea\u5305\u542b\u8d28\u56e0\u6570 2\u30013 \u548c\/\u6216 5 \u7684\u6b63\u6574\u6570\u3002
<\/em>
<\/em>
<\/em>
<\/em> \u793a\u4f8b 1\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1an = 10
<\/em> \u8f93\u51fa\uff1a12
<\/em> \u89e3\u91ca\uff1a[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] \u662f\u7531\u524d 10 \u4e2a\u4e11\u6570\u7ec4\u6210\u7684\u5e8f\u5217\u3002
<\/em> \u793a\u4f8b 2\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1an = 1
<\/em> \u8f93\u51fa\uff1a1
<\/em> \u89e3\u91ca\uff1a1 \u901a\u5e38\u88ab\u89c6\u4e3a\u4e11\u6570\u3002
<\/em>
<\/em>
<\/em> \u63d0\u793a\uff1a
<\/em>
<\/em> 1 <= n <= 1690
<\/em>
<\/em>
<\/em> * <\/em>@author <\/em><\/strong>zeroheart
<\/em> *
<\/em> *\/
<\/em>public class Question264 {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];

        dp[0] = 1;

        int q2=0;
        int q3=0;
        int q5 = 0;

        for(int i = 1; i<n; i++){
            dp[i] = Math.min<\/em>(2*dp[q2],Math.min<\/em>(3*dp[q3], 5*dp[q5]));
            if(dp[i] == 2*dp[q2]) q2++;
            if(dp[i] == 3*dp[q3]) q3++;
            if(dp[i] == 5*dp[q5]) q5++;
        }
        return dp[n-1];
    }

    public static void main(String[] args) {
    }
}<\/pre>\n\n\n\n
96. \u4e0d\u540c\u7684\u4e8c\u53c9\u641c\u7d22\u6811<\/a><\/h4>\n\n\n\n

\/**
<\/em> 96. \u4e0d\u540c\u7684\u4e8c\u53c9\u641c\u7d22\u6811
<\/em> \u7ed9\u4f60\u4e00\u4e2a\u6574\u6570 n \uff0c\u6c42\u6070\u7531 n \u4e2a\u8282\u70b9\u7ec4\u6210\u4e14\u8282\u70b9\u503c\u4ece 1 \u5230 n \u4e92\u4e0d\u76f8\u540c\u7684 \u4e8c\u53c9\u641c\u7d22\u6811 \u6709\u591a\u5c11\u79cd\uff1f\u8fd4\u56de\u6ee1\u8db3\u9898\u610f\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u79cd\u6570\u3002
<\/em>
<\/em>
<\/em>
<\/em> \u793a\u4f8b 1\uff1a
<\/em>
<\/em>
<\/em> \u8f93\u5165\uff1an = 3
<\/em> \u8f93\u51fa\uff1a5
<\/em> \u793a\u4f8b 2\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1an = 1
<\/em> \u8f93\u51fa\uff1a1
<\/em>
<\/em>
<\/em> \u63d0\u793a\uff1a
<\/em>
<\/em> 1 <= n <= 19
<\/em>
<\/em> * <\/em>@author <\/em><\/strong>zeroheart
<\/em> *
<\/em> *\/
<\/em>public class Question96 {
    public int numTrees(int n) {
        \/\/ \u771f\u4e0d\u77e5\u9053\u9012\u63a8\u516c\u5f0f\u600e\u4e48\u641e\u3002\u3002\u8bc4\u8bba\u533a\u770b\u7684
        \/\/ \u7ed3\u9898\u601d\u8def\uff1a\u5047\u8bben\u4e2a\u8282\u70b9\u5b58\u5728\u4e8c\u53c9\u6392\u5e8f\u6811\u7684\u4e2a\u6570\u662fG(n)\uff0c1\u4e3a\u6839\u8282\u70b9\uff0c2\u4e3a\u6839\u8282\u70b9\uff0c...\uff0cn\u4e3a\u6839\u8282\u70b9\uff0c\u5f531\u4e3a\u6839\u8282\u70b9\u65f6\uff0c\u5176\u5de6\u5b50\u6811\u8282\u70b9\u4e2a\u6570\u4e3a0\uff0c\u53f3\u5b50\u6811\u8282\u70b9\u4e2a\u6570\u4e3an-1\uff0c\u540c\u7406\u5f532\u4e3a\u6839\u8282\u70b9\u65f6\uff0c\u5176\u5de6\u5b50\u6811\u8282\u70b9\u4e2a\u6570\u4e3a1\uff0c\u53f3\u5b50\u6811\u8282\u70b9\u4e3an-2\uff0c\u6240\u4ee5\u53ef\u5f97G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)
        \/\/\u521d\u59cb\u5316 dp \u6570\u7ec4
        int[] dp = new int[n + 1];
        \/\/\u521d\u59cb\u53160\u4e2a\u8282\u70b9\u548c1\u4e2a\u8282\u70b9\u7684\u60c5\u51b5
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <=n; i++) {
            for (int j = 1; j <= i; j++) {
                \/\/\u5bf9\u4e8e\u7b2ci\u4e2a\u8282\u70b9\uff0c\u9700\u8981\u8003\u86511\u4f5c\u4e3a\u6839\u8282\u70b9\u76f4\u5230i\u4f5c\u4e3a\u6839\u8282\u70b9\u7684\u60c5\u51b5\uff0c\u6240\u4ee5\u9700\u8981\u7d2f\u52a0
                \/\/\u4e00\u5171i\u4e2a\u8282\u70b9\uff0c\u5bf9\u4e8e\u6839\u8282\u70b9j\u65f6,\u5de6\u5b50\u6811\u7684\u8282\u70b9\u4e2a\u6570\u4e3aj-1\uff0c\u53f3\u5b50\u6811\u7684\u8282\u70b9\u4e2a\u6570\u4e3ai-j
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
    }
}<\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
264. \u4e11\u6570 II \/** 264. \u4e11\u6570 II \u7ed9\u4f60\u4e00\u4e2a\u6574\u6570 n \uff0c\u8bf7\u4f60\u627e\u51fa\u5e76\u8fd4\u56de\u7b2c n \u4e2a \u4e11\u6570 \u3002 \u4e11 […]<\/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],"_links":{"self":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2661"}],"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=2661"}],"version-history":[{"count":4,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2661\/revisions"}],"predecessor-version":[{"id":2665,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2661\/revisions\/2665"}],"wp:attachment":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2661"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2661"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2661"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}