上一篇:算法随笔_74: 不同路径_1-CSDN博客
=====
题目描述如下:
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。
示例1:
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
=====
算法思路:
我们可以使用动态规划解决此问题。我们设res(i, j)表示从左上角到达第i行j列的格子所用的路径数。那么递推关系如下:
当obstacleGrid[i][j]不等于1时，res(i, j)=res(i, j-1)+res(i-1,j)
当obstacleGrid[i][j]等于1时，res(i, j)=0
我们可以从左上角开始遍历网格，按行遍历。设res(0, 0)=1。
时间复杂度为O(mn)。下面是Python代码实现:
class Solution(object):def uniquePathsWithObstacles(self, obstacleGrid):""":type obstacleGrid: List[List[int]]:rtype: int"""if obstacleGrid[0][0]==1:return 0m=len(obstacleGrid)n=len(obstacleGrid[0])res= [[0 for _ in range(n)] for _ in range(m)]for i in range(m):for j in range(n):if i==0 and j==0:res[i][j]=1continueif obstacleGrid[i][j]!=1: fromL=res[i][j-1] if j>0 else 0fromT=res[i-1][j] if i>0 else 0res[i][j]=fromL+fromTreturn res[m-1][n-1]关键词: 动态规划
