63.DifferentPathsII题目来源：力扣(LeetCode)https://leetcode-cn.com/problems/unique-paths-ii题目一个机器人位于一个mxn的网格中下图）。机器人一次只能向下或向右移动一步。机器人尝试到达网格的右下角（下图中标记为“完成”）。现在考虑网格中有障碍物。那么从左上角到右下角会有多少条不同的路径呢？图片来源：LeetCode63.不同路径II格子中的障碍物和空位分别用1和0表示。备注：m和n的值都不大于100。示例1：输入：[[0,0,0],[0,1,0],[0,0,0]]输出：2解释：有3x3网格正中间的障碍物。从左上角到右下角有2种不同的路径：1.Right->Right->Down->Down2.Down->Down->Right->Right解题思路：动态规划初看标题，上面写着[机器人一次只能向下或向右移动一步]。也就是说，假设我们能到达右下角终点（坐标（m,n））的路径为f(m,n)，那么到达这里的路径只能是从上或者左网格。那么，也可以得到这样一个公式：f(m,n)=f(m-1,n)+f(m,n-1)在上面公式的基础上，加上递归终止的条件。但是这个递归属于自下而上的递归，考虑改成自上而下的递归，即：dp[i][j]=dp[i-1][j]+dp[i][j-1]。这里我们首先定义状态：让dp[i][j]表示到网格(i,j)的路径数。如果格子(i,j)中有障碍物，则表示无法通过，也就是说到格子的路径数为0。此时dp[i][j]=0。如果格??子(i,j)没有障碍物，根据前面的分析，到格子(i,j)的路径来自上方或左侧。那么到达这个点的路径数等于上面的路径数加上左边的路径数之和。即：dp[i][j]=dp[i-1][j]+dp[i][j-1]则状态转移方程如下：提前补充：在实现代码执行的过程中，发现一个用例无法通过，是[[1,0]]。这意味着当起始位置有障碍时，后续无法通过。初始化dp数组，因为机器人只能向右下方移动。在grid中，第一列的grid，机器人只能从上到下移动（没有从左到右），第一行的grid，机器人只能从左到右移动（没有从上到下）。首先定义dp数组，设置值为0，初始化第一列第一行。（结合上面的补充）即：对于第一列，在没有障碍物的情况下初始化dp[i][0]=1，如果有障碍物，说明后续不能通过，后续这里不会处理；对于第一个OK，在没有障碍物的情况下初始化dp[0][j]=1，如果有障碍物，这里不做同上的处理。具体代码实现如下。输入importListclass解决方案的代码实现：defuniquePathsWithObstacles(self,obstacleGrid:List[List[int]])->int:iflen(obstacleGrid)==0ornotobstacleGrid:return0m=len(obstacleGrid)n=len(obstacleGrid[0])#首先定义dp数组dp=[[0]*nfor_inrange(m)]#初始化第一列第一行foriinrange(m):ifobstacleGrid[i][0]==1:breakdp[i][0]=1forjinrange(n):如果obstacleGrid[0][j]==1:breakdp[0][j]=1foriinrange(1,m):对于jinrange(1,n):如果obstacleGrid[i][j]==0:dp[i][j]=dp[i-1][j]+dp[i][j-1]returndp[m-1][n-1]复习题后可以得到实现结果的总结，机器人只能向右和向下移动。那么要到达终点(i,j)，只能从上方或左侧来。则设f(m,n)为到达目的地的路径数，则f(m,n)=f(m-1,n)+f(m,n-1)；上面的公式加递归属于底层向上递归，有双重计算。然后将其转换为自上而下的递归，即：dp[i][j]=dp[i-1][j]+dp[i][j-1]首先定义状态：dp[i][j]表示到(i,j)的路径数。求状态转移方程：如果(i,j)这里有障碍物，说明没有路径可以到达这里，所以dp[i][j]=0；如果(i,j)中没有障碍物，那么根据上面的分析，此时到达该点的路径数就是左边的路径数加上上面的路径数之和，即:dp[i][j]=dp[i-1][j]+dp[i][j-1]。初始化，分别处理第一行第一列（先将dp数组的值初始化为0）。因为第一行没有自上而下的路径，所以初始化dp[0][j]=1。如果有障碍物，则意味着后面的不能通过，后面的不会在这里处理；同样第一列不存在from是一条从左到右的路径，所以初始化dp[i][0]=1，如果有如上的障碍物，这里就不处理了。文章原创，如果觉得写的不错，请点个关注点个赞。微信公众号《书所集录》同步更新，欢迎关注。
