1. 题目：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
2. 我的代码：
class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: m = len(obstacleGrid) n = len(obstacleGrid[0]) # 排除特殊情况 if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1: return 0 # 定义dp数组 dp = [[0 for _ in range(n)] for _ in range(m)] # 需要让dp[0][0] = 1，为了应对只有一格的情况 dp[0][0] = 1 # 初始化dp数组 # 初始化第一行 for i in range(1, n): if obstacleGrid[0][i] == 0: dp[0][i] = 1 else: break # 初始化第一列 for j in range(1, m): if obstacleGrid[j][0] == 0: dp[j][0] = 1 else: break # 遍历 for m_i in range(1, m): for n_i in range(1, n): if obstacleGrid[m_i][n_i] == 0: dp[m_i][n_i] = dp[m_i - 1][n_i] + dp[m_i][n_i - 1] else: dp[m_i][n_i] = 0 return dp[m - 1][n - 1]
动态规划最重要最需要理清楚的点：
- dp数组及其下标的含义
- 递推公式
- dp数组初始化
- 遍历顺序
这里，通过推理得到：
- dp数组下标代表的是第几行第几列位置，dp数组的值代表的是到达该位置的路径的个数
- 递推公式，因为只能向右或者向下前进，所以，该位置可以由上面或者左面过来。因此，dp[m_i][n_i] = dp[m_i - 1][n_i] + dp[m_i][n_i - 1]。但是，这里多了障碍物，如果该位置有障碍物，需要设置dp[m_i][n_i]为0，这样别的位置从障碍物这里出发就会加0，也就是没有从障碍物来的路径。
- dp数组的初始化，我们至少要初始化第一行和第一列的所有元素，因为要推断其他位置，需要从上和左推断。第一行和第一列的元素还是比较好推断的，比如，第一列的所有元素都应该是1，因为只能从起点出发，一直向左走。从左向右遍历时，如果遇到障碍物，则需要将该位置及其后面的位置都设置为0，因为确实没有能够到达的路径。
- 遍历顺序，我们可以一行一行从上到下遍历完，或者一列一列从左到右遍历完，因为需要前面的元素去推断
