63. 不同路径 II [medium]

https://leetcode-cn.com/problems/unique-paths-ii/

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2

解释:

3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

通过次数90,776 | 提交次数249,665

First Try

2020-07-29

结合0062题，这题的关键在于障碍物如何影响初始化，考虑不周全贡献了两次错误提交。

DP公式为： dp[m][n] = dp[m][n - 1] + dp[m - 1][n]
默认第一行和第一列都是1，但是如果在第一行和第一列存在障碍物，在障碍物后面和下面就都是不可到的区域，为0
另外需要考虑初始化中待处理的元素是否已经被铺设过障碍物了，不然又被覆盖。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        """
        test case: 
        - [[0,0],[1,1],[0,0]]
        - [[1, 0]]
        """
        # dp[m][n] = dp[m][n - 1] + dp[m - 1][n]
        if not (len(obstacleGrid) and len(obstacleGrid[0])):
            return 1

        m, n = len(obstacleGrid), len(obstacleGrid[0])

        dp = [[""] * (n + 1) for _ in range(m + 1)]
        # for i in range(m + 1):
        #     dp[i][1] = 1 
        # for j in range(n + 1):
        #     dp[1][j] = 1 

        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[i + 1][j + 1] = 0 # 封堵掉障碍物

        # 不用额外处理起点和终点了，在初始化过程中考虑上障碍物就搞定了
        # 起点和终点都被封死了。 
        # if dp[1][1] == 0 or dp[m][n] == 0:
        #     return 0

        # 默认第一行和第一列都是1，但是如果在第一行和第一列存在障碍物，在障碍物后面和下面就都是不可到的区域，为0 
        # 另外需要考虑初始化中待处理的元素是否已经被铺设过障碍物了，不然又被覆盖。
        for i in range(1, m + 1):
            if dp[i][1] != 0 :  # 没有被前面障碍物处理过
                dp[i][1] = 1 if dp[i - 1][1] != 0 else 0
        for j in range(1, n + 1):
            if dp[1][j] != 0:
                dp[1][j] = 1 if dp[1][j - 1] != 0 else 0 

        def cal(m, n):
            if dp[m][n] != "":
                return dp[m][n]
            
            dp[m][n] = cal(m, n - 1) + cal(m - 1, n)
            return dp[m][n]
        
        return cal(m, n)

执行用时：44 ms, 在所有 Python3 提交中击败了58.53%的用户
内存消耗：13.8 MB, 在所有 Python3 提交中击败了14.29%的用户

官方题解中关于动态规划的小结：

回顾这道题，其实这类动态规划的题目在题库中也出现过多次，例如「221. 最大正方形」、「1162. 地图分析」等。他们都以二维坐标作为状态，大多数都可以使用滚动数组进行优化。如果我们熟悉这类问题，可以一眼看出这是一个动态规划问题。当我们不熟悉的时候，怎么想到用动态规划来解决这个问题呢？我们需要从问题本身出发，寻找一些有用的信息，例如本题中：

(i, j)(i,j) 位置只能从 (i - 1, j)(i−1,j) 和 (i, j - 1)(i,j−1) 走到，这样的条件就是在告诉我们这里转移是「无后效性」的，f(i, j)f(i,j) 和任何的 f(i', j')(i' > i, j' > j)f(i ′ ,j ′ )(i ′

i,j ′ j) 无关。动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。前者的递推性质还有一个名字，叫做「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。通常如果我们察觉到了这两点要素，这个问题八成可以用动态规划来解决。读者可以多多练习，熟能生巧。

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/unique-paths-ii/solution/bu-tong-lu-jing-ii-by-leetcode-solution-2/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

63. 不同路径 II [medium]​

First Try​

63. 不同路径 II [medium]

First Try