{"id":2774,"date":"2022-04-16T23:31:56","date_gmt":"2022-04-16T15:31:56","guid":{"rendered":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2774"},"modified":"2022-04-17T14:27:12","modified_gmt":"2022-04-17T06:27:12","slug":"dp%e7%ac%ac15%e5%a4%a9","status":"publish","type":"post","link":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2774","title":{"rendered":"dp\u7b2c15\u5929"},"content":{"rendered":"\n

62. \u4e0d\u540c\u8def\u5f84<\/a><\/p>\n\n\n\n

\u8fd9\u9898\u516c\u5f0f\u8fd8\u662f\u6bd4\u8f83\u7b80\u5355\u7684 <\/p>\n\n\n\n


\/**
<\/em> 62. \u4e0d\u540c\u8def\u5f84
<\/em> \u4e00\u4e2a\u673a\u5668\u4eba\u4f4d\u4e8e\u4e00\u4e2a m x n \u7f51\u683c\u7684\u5de6\u4e0a\u89d2 \uff08\u8d77\u59cb\u70b9\u5728\u4e0b\u56fe\u4e2d\u6807\u8bb0\u4e3a \u201cStart\u201d \uff09\u3002
<\/em>
<\/em> \u673a\u5668\u4eba\u6bcf\u6b21\u53ea\u80fd\u5411\u4e0b\u6216\u8005\u5411\u53f3\u79fb\u52a8\u4e00\u6b65\u3002\u673a\u5668\u4eba\u8bd5\u56fe\u8fbe\u5230\u7f51\u683c\u7684\u53f3\u4e0b\u89d2\uff08\u5728\u4e0b\u56fe\u4e2d\u6807\u8bb0\u4e3a \u201cFinish\u201d \uff09\u3002
<\/em>
<\/em> \u95ee\u603b\u5171\u6709\u591a\u5c11\u6761\u4e0d\u540c\u7684\u8def\u5f84\uff1f
<\/em>
<\/em>
<\/em>
<\/em> \u793a\u4f8b 1\uff1a
<\/em>
<\/em>
<\/em> \u8f93\u5165\uff1am = 3, n = 7
<\/em> \u8f93\u51fa\uff1a28
<\/em> \u793a\u4f8b 2\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1am = 3, n = 2
<\/em> \u8f93\u51fa\uff1a3
<\/em> \u89e3\u91ca\uff1a
<\/em> \u4ece\u5de6\u4e0a\u89d2\u5f00\u59cb\uff0c\u603b\u5171\u6709 3 \u6761\u8def\u5f84\u53ef\u4ee5\u5230\u8fbe\u53f3\u4e0b\u89d2\u3002
<\/em> 1. \u5411\u53f3 -> \u5411\u4e0b -> \u5411\u4e0b
<\/em> 2. \u5411\u4e0b -> \u5411\u4e0b -> \u5411\u53f3
<\/em> 3. \u5411\u4e0b -> \u5411\u53f3 -> \u5411\u4e0b
<\/em> \u793a\u4f8b 3\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1am = 7, n = 3
<\/em> \u8f93\u51fa\uff1a28
<\/em> \u793a\u4f8b 4\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1am = 3, n = 3
<\/em> \u8f93\u51fa\uff1a6
<\/em>
<\/em>
<\/em> \u63d0\u793a\uff1a
<\/em>
<\/em> 1 <= m, n <= 100
<\/em> \u9898\u76ee\u6570\u636e\u4fdd\u8bc1\u7b54\u6848\u5c0f\u4e8e\u7b49\u4e8e 2 * 10^9
<\/em>
<\/em>
<\/em> * <\/em>@author <\/em><\/strong>zeroheart
<\/em> *
<\/em> *\/
<\/em>
<\/em>
<\/em>public class Question62 {
    public int uniquePaths(int m, int n) {

        \/\/ dp[i][j] = dp[i-1][j]+dp[i][j-1]
        int[][] dp = new int[m][n];
        for(int i = 0; i<m; i++) dp[i][0] = 1;
        for(int j = 0; j<n; j++) dp[0][j] = 1;

        for(int i = 1; i<m; i++){
            for(int j = 1; j<n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
    }
}<\/pre>\n\n\n\n
63. \u4e0d\u540c\u8def\u5f84 II<\/a><\/p>\n\n\n\n
\u5b58\u5728\u969c\u788d\u7269\uff0c\u6ce8\u610f\u53ea\u80fd\u5411\u53f3\u548c\u5411\u4e0b\u8d70\uff0c\u6240\u6709[0][j]\u548c[i][0]\u9047\u5230\u969c\u788d\u5c31break\u4e86<\/p>\n\n\n\n
\n\/**\n<\/em> 63. \u4e0d\u540c\u8def\u5f84 II\n<\/em> \u4e00\u4e2a\u673a\u5668\u4eba\u4f4d\u4e8e\u4e00\u4e2a m x n \u7f51\u683c\u7684\u5de6\u4e0a\u89d2 \uff08\u8d77\u59cb\u70b9\u5728\u4e0b\u56fe\u4e2d\u6807\u8bb0\u4e3a \u201cStart\u201d \uff09\u3002\n<\/em>\n<\/em> \u673a\u5668\u4eba\u6bcf\u6b21\u53ea\u80fd\u5411\u4e0b\u6216\u8005\u5411\u53f3\u79fb\u52a8\u4e00\u6b65\u3002\u673a\u5668\u4eba\u8bd5\u56fe\u8fbe\u5230\u7f51\u683c\u7684\u53f3\u4e0b\u89d2\uff08\u5728\u4e0b\u56fe\u4e2d\u6807\u8bb0\u4e3a \u201cFinish\u201d\uff09\u3002\n<\/em>\n<\/em> \u73b0\u5728\u8003\u8651\u7f51\u683c\u4e2d\u6709\u969c\u788d\u7269\u3002\u90a3\u4e48\u4ece\u5de6\u4e0a\u89d2\u5230\u53f3\u4e0b\u89d2\u5c06\u4f1a\u6709\u591a\u5c11\u6761\u4e0d\u540c\u7684\u8def\u5f84\uff1f\n<\/em>\n<\/em> \u7f51\u683c\u4e2d\u7684\u969c\u788d\u7269\u548c\u7a7a\u4f4d\u7f6e\u5206\u522b\u7528 1 \u548c 0 \u6765\u8868\u793a\u3002\n<\/em>\n<\/em>\n<\/em>\n<\/em> \u793a\u4f8b 1\uff1a\n<\/em>\n<\/em>\n<\/em> \u8f93\u5165\uff1aobstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]\n<\/em> \u8f93\u51fa\uff1a2\n<\/em> \u89e3\u91ca\uff1a3x3 \u7f51\u683c\u7684\u6b63\u4e2d\u95f4\u6709\u4e00\u4e2a\u969c\u788d\u7269\u3002\n<\/em> \u4ece\u5de6\u4e0a\u89d2\u5230\u53f3\u4e0b\u89d2\u4e00\u5171\u6709 2 \u6761\u4e0d\u540c\u7684\u8def\u5f84\uff1a\n<\/em> 1. \u5411\u53f3 -> \u5411\u53f3 -> \u5411\u4e0b -> \u5411\u4e0b\n<\/em> 2. \u5411\u4e0b -> \u5411\u4e0b -> \u5411\u53f3 -> \u5411\u53f3\n<\/em> \u793a\u4f8b 2\uff1a\n<\/em>\n<\/em>\n<\/em> \u8f93\u5165\uff1aobstacleGrid = [[0,1],[0,0]]\n<\/em> \u8f93\u51fa\uff1a1\n<\/em>\n<\/em>\n<\/em> \u63d0\u793a\uff1a\n<\/em>\n<\/em> m == obstacleGrid.length\n<\/em> n == obstacleGrid[i].length\n<\/em> 1 <= m, n <= 100\n<\/em> obstacleGrid[i][j] \u4e3a 0 \u6216 1\n<\/em>\n<\/em>\n<\/em> * <\/em>@author <\/em><\/strong>zeroheart\n<\/em> *\n<\/em> *\/\n<\/em>\n<\/em>\n<\/em>public class Question63 {\n\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n        int m = obstacleGrid.length;\n        int n = obstacleGrid[0].length;\n\n        int[][] dp = new int[m][n];\n\n        for(int i = 0; i<m; i++){\n            if(obstacleGrid[i][0] == 1) {\n                break;\n            }else{\n                dp[i][0] = 1;\n            }\n        }\n\n        for(int j = 0; j<n; j++){\n            if(obstacleGrid[0][j] == 1) {\n                break;\n            }else{\n                dp[0][j] = 1;\n            }\n        }\n\n\n        for(int i = 1; i<m; i++){\n            for(int j = 1; j<n; j++){\n                if(obstacleGrid[i][j] == 1) {\n                    continue;\n                }else{\n                    dp[i][j] = dp[i-1][j] + dp[i][j-1];\n                }\n            }\n        }\n\n        return dp[m-1][n-1];\n    }\n\n    public static void main(String[] args) {\n    }\n}<\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
62. \u4e0d\u540c\u8def\u5f84 \u8fd9\u9898\u516c\u5f0f\u8fd8\u662f\u6bd4\u8f83\u7b80\u5355\u7684 \/** 62. \u4e0d\u540c\u8def\u5f84 \u4e00\u4e2a\u673a\u5668\u4eba\u4f4d\u4e8e\u4e00\u4e2a m x n \u7f51\u683c\u7684\u5de6\u4e0a […]<\/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\/2774"}],"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=2774"}],"version-history":[{"count":7,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2774\/revisions"}],"predecessor-version":[{"id":2782,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2774\/revisions\/2782"}],"wp:attachment":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2774"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2774"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2774"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}