Update 62.unique-paths.md

azl397985856 · web-flow · commit d71918eb6c55 · 2020-02-10T12:24:42.000+08:00
diff --git a/problems/62.unique-paths.md b/problems/62.unique-paths.md
@@ -34,8 +34,8 @@ Output: 28
 ```
 
 ## 思路
-这是一道典型的适合使用动态规划解决的题目，它和爬楼梯等都属于动态规划中最简单的题目，
-因此也经常会被用于面试之中。
+
+这是一道典型的适合使用动态规划解决的题目，它和爬楼梯等都属于动态规划中最简单的题目，因此也经常会被用于面试之中。
 
 读完题目你就能想到动态规划的话，建立模型并解决恐怕不是难事。其实我们很容易看出，由于机器人只能右移动和下移动，
 因此第[i, j]个格子的总数应该等于[i - 1, j] + [i, j -1]， 因为第[i,j]个格子一定是从左边或者上面移动过来的。
@@ -44,6 +44,8 @@ Output: 28
 
 代码大概是：
 
+JS Code:
+
 ```js
  const dp = [];
   for (let i = 0; i < m + 1; i++) {
@@ -63,16 +65,56 @@ Output: 28
 
 ```
 
+Python Code:
+
+```python
+class Solution:
+    def uniquePaths(self, m: int, n: int) -> int:
+        d = [[1] * n for _ in range(m)]
+
+        for col in range(1, m):
+            for row in range(1, n):
+                d[col][row] = d[col - 1][row] + d[col][row - 1]
+
+        return d[m - 1][n - 1]
+ ```
+ 
+ **复杂度分析**
+ 
+ - 时间复杂度：$O(M * N)$
+ - 空间复杂度：$O(M * N)$
+
 由于dp[i][j] 只依赖于左边的元素和上面的元素，因此空间复杂度可以进一步优化， 优化到O(n).
 
 ![62.unique-paths-3](../assets/problems/62.unique-paths-3.png)
 
 具体代码请查看代码区。
 
+
+当然你也可以使用记忆化递归的方式来进行，由于递归深度的原因，性能比上面的方法差不少：
+
+> 直接暴力递归的话会超时。
+
+Python3 Code:
+```python
+class Solution:
+    visited = dict()
+
+    def uniquePaths(self, m: int, n: int) -> int:
+        if (m, n) in self.visited:
+            return self.visited[(m, n)]
+        if m == 1 or n == 1:
+            return 1
+        cnt = self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)
+        self.visited[(m, n)] = cnt
+        return cnt
+ ```
+
 ## 关键点
 
-- 空间复杂度可以进一步优化到O(n), 这会是一个考点
+- 记忆化递归
 - 基本动态规划问题
+- 空间复杂度可以进一步优化到O(n), 这会是一个考点
 ## 代码
 
 ```js
@@ -82,47 +124,6 @@ Output: 28
  * [62] Unique Paths
  *
  * https://leetcode.com/problems/unique-paths/description/
- *
- * algorithms
- * Medium (46.53%)
- * Total Accepted:    277K
- * Total Submissions: 587.7K
- * Testcase Example:  '3\n2'
- *
- * A robot is located at the top-left corner of a m x n grid (marked 'Start' in
- * the diagram below).
- *
- * The robot can only move either down or right at any point in time. The robot
- * is trying to reach the bottom-right corner of the grid (marked 'Finish' in
- * the diagram below).
- *
- * How many possible unique paths are there?
- *
- *
- * Above is a 7 x 3 grid. How many possible unique paths are there?
- *
- * Note: m and n will be at most 100.
- *
- * Example 1:
- *
- *
- * Input: m = 3, n = 2
- * Output: 3
- * Explanation:
- * From the top-left corner, there are a total of 3 ways to reach the
- * bottom-right corner:
- * 1. Right -> Right -> Down
- * 2. Right -> Down -> Right
- * 3. Down -> Right -> Right
- *
- *
- * Example 2:
- *
- *
- * Input: m = 7, n = 3
- * Output: 28
- *
- *   START
  */
 /**
  * @param {number} m
@@ -141,3 +142,8 @@ var uniquePaths = function(m, n) {
   return dp[n - 1];
 };
 ```
+
+ **复杂度分析**
+ 
+ - 时间复杂度：$O(M * N)$
+ - 空间复杂度：$O(N)$
