线性动态规划：计算网格中从起点到终点的不同路径数（有障碍物）
题目描述：
在一个 m×n 的网格中，一个机器人从左上角 (0,0) 出发，每次只能向右或向下移动一步，试图到达右下角 (m-1,n-1)。网格中可能存在障碍物（用 1 表示），空位置用 0 表示。你需要计算机器人从起点到终点的不同路径数量。注意：网格中的障碍物会阻挡机器人通过，如果起点或终点有障碍物，则路径数为 0。
示例：
输入：
网格 = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
网格中有一个障碍物在 (1,1)，机器人可能的路径为：
- 右 → 右 → 下 → 下
- 下 → 下 → 右 → 右
解题过程循序渐进讲解：
步骤 1：问题理解与状态定义
这是一个经典的网格路径计数问题，但增加了障碍物限制。机器人只能向右或向下移动，意味着到达某个格子 (i,j) 的路径只能从其左侧 (i,j-1) 或上方 (i-1,j) 过来。因此，我们可以定义动态规划的状态：
令 dp[i][j] 表示从起点 (0,0) 到达格子 (i,j) 的不同路径数。
目标：求 dp[m-1][n-1]。
步骤 2：确定状态转移方程
对于每个格子 (i,j)，考虑两种情况：
- 如果该格子是障碍物（值为 1），则没有路径能到达这里，
dp[i][j] = 0。 - 否则，如果该格子为空（值为 0），则路径数等于从上方来的路径数加上从左方来的路径数：
dp[i][j] = dp[i-1][j] + dp[i][j-1]。
但需要注意边界情况：当 i=0 或 j=0 时，只能从一个方向来（第一行只能从左方来，第一列只能从上方来），除非该方向被障碍物阻挡。
步骤 3：处理边界与初始化
初始状态：起点 (0,0)。
- 如果起点是障碍物，直接返回 0，因为无法出发。
- 否则，
dp[0][0] = 1。
对于第一行（i=0，j>0）：只能从左方来，所以dp[0][j] = dp[0][j-1]（如果当前格非障碍物）。如果左方是 0（无障碍），则延续路径数；如果左方是障碍物，则路径中断，后面全部为 0。
对于第一列（j=0，i>0）：类似处理，只能从上方来。
步骤 4：动态规划计算顺序
按照从上到下、从左到右的顺序遍历网格，依次计算每个格子的 dp[i][j]。这样可以保证在计算 (i,j) 时，其上方和左方的值已经计算完毕。
步骤 5：示例推演（用上面的例子）
网格：
0 0 0
0 1 0
0 0 0
初始化 dp[0][0] = 1。
第一行：
dp[0][1] = dp[0][0] = 1
dp[0][2] = dp[0][1] = 1
第一列：
dp[1][0] = dp[0][0] = 1
dp[2][0] = dp[1][0] = 1
其余位置：
dp[1][1] 是障碍物，直接为 0。
dp[1][2] = dp[0][2] + dp[1][1] = 1 + 0 = 1
dp[2][1] = dp[1][1] + dp[2][0] = 0 + 1 = 1
dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2
最终结果为 dp[2][2] = 2。
步骤 6：边界情况与优化
- 如果终点是障碍物，直接返回 0。
- 由于每个状态只依赖于上一行和当前行的左侧，可以将空间复杂度优化为 O(n)（只保留一行或一列的状态），但为了清晰，我们先使用二维数组讲解。
步骤 7：写出伪代码
function uniquePathsWithObstacles(grid):
m = grid.length, n = grid[0].length
if grid[0][0] == 1 or grid[m-1][n-1] == 1:
return 0
dp = 二维数组大小 m×n，初始化为 0
dp[0][0] = 1
for i in 0 to m-1:
for j in 0 to n-1:
if grid[i][j] == 1:
dp[i][j] = 0
else:
if i > 0:
dp[i][j] += dp[i-1][j]
if j > 0:
dp[i][j] += dp[i][j-1]
return dp[m-1][n-1]
步骤 8：复杂度分析
时间复杂度：O(m×n)，因为遍历整个网格一次。
空间复杂度：O(m×n)（可以优化到 O(n) 或 O(min(m,n))）。
步骤 9：扩展思考
- 如果允许向上、向左移动（但不能重复访问格子），问题会变成哈密顿路径问题，不再是简单动态规划。
- 如果网格非常大，可以考虑用记忆化搜索（递归+缓存）实现，但本质思想相同。
- 如果要求输出所有具体路径，则需要用回溯法，但会指数级增长。
通过以上步骤，我们完整解决了带障碍物的不同路径计数问题。核心是利用动态规划，根据移动方向递推，并小心处理障碍物导致的路径中断。