63. 不同路径II

题目描述

示例：

输入:[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

官方思路

没错，这题又没自己的思路，确认过眼神，是我做不出的题。说来惭愧，已经连着刷了三天的动态规划，依然没什么长进，拿到题还想用回溯法来做（可能受剑指offer最后一题的影响，我现在还相信回溯法可以解，但是我回溯法也很渣，就没做出来），这么明显的动态规划，硬硬是没看出来。其实题目并不难，毕竟只是中等难度，稍稍瞟一下官方思路就知道怎么解了。没想出来一来是因为练得少，对动态规划还是没法一下反应过来，二来是真的一开始思路就跑偏了。话说这题真的和剑指offer最后一题好像啊。。。

言归正传，刚才有提到用动态规划来求解。创建一个二维列表dp，与题目给出的地图矩阵尺寸相对应，dp[i][j]记录地图上到达(i, j)点可选的路径条数。注意，在之前我们创建状态矩阵dp的时候都会大一号用来记录初状态，这道题并不需要，至于原因我们在说到初条件的时候会具体解释。

老套路，说到动态规划首先要确定状态转移方程。首先，我们可以分为两种情况考虑：1. 地图上(i, j)点为1，即(i, j)点是有障碍的，那么这个点无论如何都是无法到达的，没有可选的路径，即dp[i][j] = 0；2. 地图上(i, j)点为0，通行无阻，那么dp[i][j]的值取决于(i, j)点左边和上边点的状态，即(i-1, j)和(i, j-1)点的状态，因为机器人只能向下或者向右走。进一步，(i, j)点可选择的走法就是左边和上边可选择走法的和，即dp[i][j] = dp[i-1][j] + dp[i][j-1]。至此，状态转移方程已经确定，很简单有木有。

其次是初条件，也就是边界。首先dp[0][0] = 1毫无疑问，因为在左上角上你只能往这一站，没啥别的路到这。其次就是第一行的所有元素dp[0][j]，只要没障碍，想到达第一行的任意一点都只能向右走这一条路，即只要地图上(0, j)没碰到1，dp[0][j]就都是1；要是碰上障碍，那第一行之后的点也都无法到达，则剩余dp值都置0，但是由于我们初始化状态矩阵dp时就全部置0了，所以在代码上可以省略。而第一列的情况与第一行的情况类似，思路一样，不做赘述。那么我们之前创建状态矩阵都会大一号来为初条件预留位置，但是为什么这次没有。因为我们的初条件已经被包括进矩阵中了，这题的边界就是实实在在机器人站在地图左和上边界的位置上啊，所以我们没有再预留。而像昨天的题，这里回顾一下，初条件是子串为空的情况，很明显在创建状态矩阵时没有考虑进去，需要单独加一下。先不全面地总结一下：像是这种计算有多少种情况啊路径啊的动态规划，状态矩阵可能不需要预留初条件的空间；而像那种计算最长啊是否成立啊的动态规划，可能就需要状态矩阵预留一下初条件的空间。或者说这种给出地图的题目，就不需要预留；而那种由字符串或者数组什么的转化的，状态矩阵仅仅是用来记录的，可能就需要预留。说的一不一定对，毕竟做的题还是太少。且做且总结吧，自己把自己推翻也说不定。

最后我们只要返回最角上的路径数就可以了，即dp[-1][-1]。

题解代码：

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:if obstacleGrid[0][0] == 1:  # 这里我是真没想到把入口给堵死了，敢问机器人咋站进去的？？？return 0# 创建状态矩阵m = len(obstacleGrid)n = len(obstacleGrid[0])dp = [[0 for _ in range(n)] for _ in range(m)]# 设定初条件dp[0][0] = 1  # 原点for i in range(1,m):  # 第一列if obstacleGrid[i][0] == 0:dp[i][0] = 1else:breakfor j in range(1,n): # 第一行if obstacleGrid[0][j] == 0:dp[0][j] = 1else:break# 状态转移并记录for i in range(1,m):for j in range(1,n):if obstacleGrid[i][j] == 0:dp[i][j] =  dp[i-1][j] + dp[i][j-1]return dp[-1][-1]

这么做时间和空间复杂度都是 O(mn)。依然觉得，只需要记录并一直迭代维护的dp[i][j-1]和dp[i-1][j-1]即可，降低空间复杂度。看了题解也的确是可行的，有点懒了而且最近事有点多，就没有具体写。

运行结果：

以上就是我，一个正儿八经的小白（大神们通过看代码应该也感觉出来了），对这道题的理解，欢迎诸位指正讨论，感谢阅读。

原题链接：

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