62 63 递归 + dp

lection · lection · commit b09b09193e7f · 2019-07-19T01:47:18.000+08:00
diff --git a/Week_04/id_3/dp/LeetCode_62_3_v1.py b/Week_04/id_3/dp/LeetCode_62_3_v1.py
@@ -0,0 +1,50 @@
+"""
+一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
+
+机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
+
+问总共有多少条不同的路径？
+
+例如，上图是一个7 x 3 的网格。有多少可能的路径？
+
+说明：m 和 n 的值均不超过 100。
+
+示例 1:
+
+输入: m = 3, n = 2
+输出: 3
+解释:
+从左上角开始，总共有 3 条路径可以到达右下角。
+1. 向右 -> 向右 -> 向下
+2. 向右 -> 向下 -> 向右
+3. 向下 -> 向右 -> 向右
+示例 2:
+
+输入: m = 7, n = 3
+输出: 28
+===========================
+老套路先试试回溯+缓存
+优化 碰触到右或者下的边可直接返回1
+缓存为m*n数组，mn启点 00终点，这样变量能少传两个。
+"""
+
+
+class Solution:
+    def uniquePaths(self, m: int, n: int) -> int:
+        if not m or not n:
+            return 0
+        return self.rec(m-1, n-1, [[None for _ in range(n)] for _ in range(m)])
+
+    def rec(self, m, n, cache):
+        if not m or not n:
+            return 1
+
+        if cache[m][n] is None:
+            cache[m][n] = self.rec(m-1, n, cache) + self.rec(m, n-1, cache)
+
+        return cache[m][n]
+
+
+s = Solution()
+print(s.uniquePaths(3, 2) == 3)
+print(s.uniquePaths(7, 3) == 28)
diff --git a/Week_04/id_3/dp/LeetCode_62_3_v2.py b/Week_04/id_3/dp/LeetCode_62_3_v2.py
@@ -0,0 +1,26 @@
+"""
+老套路 DP递推 自底向上
+00默认是终点递推比较容易
+"""
+
+
+class Solution:
+    def uniquePaths(self, m: int, n: int) -> int:
+        if not m or not n:
+            return 0
+
+        cache = [1] * n
+        for _m in range(1, m):
+            _cache = [1] * n
+            for _n in range(1, n):
+                _cache[_n] = _cache[_n-1] + cache[_n]
+
+            cache = _cache
+
+        return cache[n - 1]
+
+
+s = Solution()
+print(s.uniquePaths(3, 2) == 3)
+print(s.uniquePaths(7, 3) == 28)
+print(s.uniquePaths(3, 7) == 28)
diff --git a/Week_04/id_3/dp/LeetCode_63_3_v1.py b/Week_04/id_3/dp/LeetCode_63_3_v1.py
@@ -0,0 +1,49 @@
+"""
+一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
+
+机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
+
+现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
+
+===================================
+老套路 先递归
+直接用初始化数组当缓存
+用None取代本来是结果0的点位 避免重复计算 -1取代障碍物点位
+"""
+
+
+class Solution:
+    def uniquePathsWithObstacles(self, obstacleGrid) -> int:
+        if not obstacleGrid or not obstacleGrid[0]:
+            return 0
+
+        for m in range(len(obstacleGrid)):
+            for n in range(len(obstacleGrid[0])):
+                obstacleGrid[m][n] = None if obstacleGrid[m][n] == 0 else -1
+
+        return self.rec(0, 0, len(obstacleGrid)-1, len(obstacleGrid[0])-1, obstacleGrid)
+
+    def rec(self, m, n, m_max, n_max, grid):
+        if m > m_max or n > n_max:
+            return 0
+
+        if grid[m][n] == -1:
+            return 0
+
+        if m == m_max and n == n_max:
+            return 1
+
+        if grid[m][n] is None:
+            grid[m][n] = self.rec(m+1, n, m_max, n_max, grid) + self.rec(m, n+1, m_max, n_max, grid)
+
+        return grid[m][n]
+
+
+s = Solution()
+print(s.uniquePathsWithObstacles([
+    [0, 0, 0],
+    [0, 1, 0],
+    [0, 0, 0]
+]))
+print(s.uniquePathsWithObstacles([[1, 0]]))
+print(s.uniquePathsWithObstacles([[0, 1]]))
diff --git a/Week_04/id_3/dp/LeetCode_63_3_v2.py b/Week_04/id_3/dp/LeetCode_63_3_v2.py
@@ -0,0 +1,36 @@
+"""
+尝试DP
+"""
+
+
+class Solution:
+    def uniquePathsWithObstacles(self, grid) -> int:
+        if not grid or not grid[0]:
+            return 0
+
+        for m in range(len(grid)):
+            for n in range(len(grid[0])):
+                if grid[m][n] == 1:
+                    grid[m][n] = 0
+                    continue
+
+                if m == 0 and n == 0:
+                    grid[m][n] = 1
+                    continue
+
+                if n > 0:
+                    grid[m][n] += grid[m][n-1]
+                if m > 0:
+                    grid[m][n] += grid[m-1][n]
+
+        return grid[m][n]
+
+
+s = Solution()
+print(s.uniquePathsWithObstacles([
+    [0, 0, 0],
+    [0, 1, 0],
+    [0, 0, 0]
+]))
+print(s.uniquePathsWithObstacles([[1, 0]]))
+print(s.uniquePathsWithObstacles([[0, 1]]))
