\u7ed9\u5b9a\u4e00\u4e2a\u5305\u542b\u975e\u8d1f\u6574\u6570\u7684 m x n \u7f51\u683c grid \uff0c\u8bf7\u627e\u51fa\u4e00\u6761\u4ece\u5de6\u4e0a\u89d2\u5230\u53f3\u4e0b\u89d2\u7684\u8def\u5f84\uff0c\u4f7f\u5f97\u8def\u5f84\u4e0a\u7684\u6570\u5b57\u603b\u548c\u4e3a\u6700\u5c0f\u3002
\n\u8bf4\u660e\uff1a\u6bcf\u6b21\u53ea\u80fd\u5411\u4e0b\u6216\u8005\u5411\u53f3\u79fb\u52a8\u4e00\u6b65\u3002<\/p>\n
\u793a\u4f8b\uff1a
\n\u8f93\u5165\uff1agrid = [[1,3,1],[1,5,1],[4,2,1]]
\n\u8f93\u51fa\uff1a7<\/p>\n
\u52a8\u6001\u89c4\u5212 \u65f6\u95f4\u590d\u6742\u5ea6 O(m * n)<\/p>\n \u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u4e00\u4e2a\u5305\u542b\u975e\u8d1f\u6574\u6570\u7684 m x n \u7f51\u683c grid \uff0c\u8bf7\u627e\u51fa\u4e00\u6761\u4ece\u5de6\u4e0a\u89d2\u5230\u53f3\u4e0b\u89d2\u7684\u8def\u5f84\uff0c\u4f7f\u5f97\u8def\u5f84\u4e0a\u7684 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[20,40],"class_list":["post-1047","post","type-post","status-publish","format-standard","hentry","category-algo","tag-leetcode","tag-40"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1047","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1047"}],"version-history":[{"count":1,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1047\/revisions"}],"predecessor-version":[{"id":1048,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1047\/revisions\/1048"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1047"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1047"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1047"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n\u8bbe dp[i][j] \u8868\u793a\u79fb\u52a8\u81f3 i, j \u6240\u9700\u7684\u6700\u5c0f\u603b\u548c\uff0c\u5219 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]<\/code>\u3002
\n\u53ef\u4ee5\u5c06\u7a7a\u95f4\u4f18\u5316\u4e3a\u4e00\u7ef4\uff0c dp[j] = min(dp[j], dp[j-1]) + grid[i][j]<\/code>\u3002<\/p>\nJava<\/h1>\n
public int minPathSum(int[][] grid) {\n int m = grid.length, n = grid[0].length;\n int[] dp = new int[n];\n dp[0] = grid[0][0];\n for (int i = 0; i < m; i++) {\n for (int j = 0; j < n; j++) {\n if (i == 0 && j == 0) {\n continue;\n }\n int left = j >= 1 ? dp[j - 1] : Integer.MAX_VALUE;\n int up = i >= 1 ? dp[j] : Integer.MAX_VALUE;\n dp[j] = Math.min(left, up) + grid[i][j];\n }\n }\n return dp[n - 1];\n}\n<\/code><\/pre>\nKotlin<\/h1>\n
fun minPathSum(grid: Array<IntArray>): Int {\n val m = grid.size\n val n = grid[0].size\n val dp = IntArray(n)\n dp[0] = grid[0][0]\n for (i in 0 until m) {\n for (j in 0 until n) {\n if (i == 0 && j == 0) continue\n dp[j] = min(if (i >= 1) dp[j] else Int.MAX_VALUE, if (j >= 1) dp[j - 1] else Int.MAX_VALUE) + grid[i][j]\n }\n }\n return dp[n - 1]\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"