Merge remote-tracking branch 'origin/master'

yuanguangxin · yuanguangxin · commit c25b95e6b519 · 2020-03-30T22:06:22.000+08:00
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/README.md b/README.md
@@ -87,6 +87,7 @@
 
 * [q5_最长回文子串](/src/动态规划/q5_最长回文子串)
 * [q53_最大子序和](/src/动态规划/q53_最大子序和)
+* [q62_不同路径](/src/动态规划/q62_不同路径)
 * [q64_最小路径和](/src/动态规划/q64_最小路径和)
 * [q70_爬楼梯](/src/动态规划/q70_爬楼梯)
 * [q118_杨辉三角](/src/动态规划/q118_杨辉三角)
diff --git a/src/动态规划/q62_不同路径/Solution.java b/src/动态规划/q62_不同路径/Solution.java
@@ -0,0 +1,26 @@
+package 动态规划.q62_不同路径;
+
+/**
+ * 动态规划 dp[i][j]是到达i, j的最多路径 dp[i][j] = dp[i-1][j] + dp[i][j-1] o(m*n)
+ */
+public class Solution {
+
+    public int uniquePaths(int m, int n) {
+        if (m < 1 || n < 1) {
+            return 0;
+        }
+        int[][] dp = new int[m][n];
+        for (int i = 0; i < n; i++) {
+            dp[0][i] = 1;
+        }
+        for (int i = 0; i < m; i++) {
+            dp[i][0] = 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];
+    }
+}
