\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\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\u95ee\u603b\u5171\u6709\u591a\u5c11\u6761\u4e0d\u540c\u7684\u8def\u5f84\uff1f<\/p>\n
\u793a\u4f8b\uff1a
\n\u8f93\u5165\uff1am = 3, n = 7
\n\u8f93\u51fa\uff1a28<\/p>\n
\u8bbe dp[i][j] \u8868\u793a\u79fb\u52a8\u81f3 i, j \u7684\u8def\u5f84\u6761\u6570\uff0c \u65f6\u95f4\u590d\u6742\u5ea6 O(m * n)<\/p>\n \u4e00\u5171\u9700\u8981\u79fb\u52a8 m + n – 2 \u6b21\uff0c\u6a2a\u5411 n – 1 \u6b21\uff0c\u7eb5\u5411 m – 1 \u6b21 \u65f6\u95f4\u590d\u6742\u5ea6 O(min(m, n))<\/p>\n \u9898\u76ee\u63cf\u8ff0 \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 \u673a\u5668\u4eba\u6bcf […]<\/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,82,91],"class_list":["post-1045","post","type-post","status-publish","format-standard","hentry","category-algo","tag-leetcode","tag-40","tag-82","tag-91"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1045","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=1045"}],"version-history":[{"count":1,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1045\/revisions"}],"predecessor-version":[{"id":1046,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1045\/revisions\/1046"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1045"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1045"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1045"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}dp[i][j] = dp[i-1][j] + dp[i][j-1]<\/code>
\n\u53ef\u8fdb\u4e00\u6b65\u5c06\u7a7a\u95f4\u4f18\u5316\u4e3a\u4e00\u5c42 dp[j] = dp[j] + dp[j - 1]<\/code><\/p>\n\u6570\u5b66<\/h2>\n
\n\u95ee\u9898\u8f6c\u5316\u4e3a\u4ece m + n – 2 \u6b21\u4e2d\u9009\u62e9 n – 1 \u6b21\uff0c\u5373 C(m + n – 2, n – 1)
\nC(m, n) = A(m, n) \/ A(n, n)\uff0c\u6570\u636e\u91cf\u5927\u4f1a\u6ea2\u51fa\uff0c\u4e0d\u80fd\u5206\u5f00\u8ba1\u7b97\uff0c\u9700\u8981\u7ed3\u5408\u5728\u4e00\u8d77\u8ba1\u7b97\u3002<\/p>\nJava<\/h1>\n
public int uniquePaths(int m, int n) {\n if (m < n) {\n int temp = m;\n m = n;\n n = temp;\n }\n int sum = m + n - 2;\n int col = n - 1;\n long ans = 1;\n for (int i = sum, j = 1; i > sum - col; i--, j++) {\n ans *= i;\n ans \/= j;\n }\n return (int) ans;\n}\n\npublic int uniquePaths2(int m, int n) {\n int[] dp = new int[n];\n dp[0] = 1;\n for (int i = 0; i < m; i++) {\n for (int j = 1; j < n; j++) {\n dp[j] += dp[j - 1];\n }\n }\n return dp[n - 1];\n}\n<\/code><\/pre>\nKotlin<\/h1>\n
fun uniquePaths(m: Int, n: Int): Int {\n val a = if (m < n) n else m\n val b = if (m < n) m else n\n val sum = a + b - 2\n val col = b - 1\n var ans = 1L\n var j = 1\n for (i in sum downTo sum - col + 1) {\n ans *= i\n ans \/= j++\n }\n return ans.toInt()\n}\n\nfun uniquePaths2(m: Int, n: Int): Int {\n val dp = Array(m) { IntArray(n) }\n dp[0][0] = 1\n for (i in 0 until m) {\n for (j in 0 until n) {\n if (i == 0 && j == 0) {\n continue\n }\n val up = if (i >= 1) dp[i - 1][j] else 0\n val left = if (j >= 1) dp[i][j - 1] else 0\n dp[i][j] = up + left\n }\n }\n return dp[m - 1][n - 1]\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"