力扣第 63 题不同路径 II

题目描述

一个机器人位于一个 $m\times n$ 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或向右移动一步。机器人试图到达网格的右下角（标记为 “Finish”）。

现在考虑网格中有障碍物。网格中的障碍物和空位置分别用 1 和 0 表示。
问总共有多少条不同的路径从左上角到右下角？

示例 1:

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

示例 2:

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示:

• $m==obstacleGrid.length$
• $n==obstacleGrid[i].length$
• $1\le m,n\le 100$
• obstacleGrid[i][j] 为 0 或 1。

解题思路

这一题的核心思路是动态规划，但需要处理障碍物。障碍物会使路径数变为 0，因此在动态规划中需要特别处理障碍物的情况。

动态规划解法

1. 定义状态：

   • 令 dp[i][j] 表示从起点到网格位置 $(i,j)$ 的不同路径数。

2. 状态转移方程：

   • 如果当前网格位置 $(i,j)$ 没有障碍物：
     dp[i][j] = dp[i-1][j] + dp[i][j-1]
   • 如果当前网格位置 $(i,j)$ 有障碍物：
     dp[i][j] = 0

3. 初始化：

   • 如果起点 obstacleGrid[0][0] == 1，直接返回 0，因为起点被障碍物挡住。
   • 第一行和第一列的路径数需要单独处理，只有在没有障碍物的情况下路径数为 1，否则为 0。

4. 结果：

   • 最终答案为 dp[m-1][n-1]。

C 代码实现

二维动态规划

#include <stdio.h>
#include <stdlib.h>

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize) {
    int m = obstacleGridSize;       // 行数
    int n = *obstacleGridColSize;   // 列数

    // 如果起点有障碍物，直接返回 0
    if (obstacleGrid[0][0] == 1) {
        return 0;
    }

    // 动态规划数组
    int dp[m][n];

    // 初始化
    dp[0][0] = 1; // 起点路径数为 1
    for (int i = 1; i < m; i++) {
        dp[i][0] = (obstacleGrid[i][0] == 1) ? 0 : dp[i-1][0];
    }
    for (int j = 1; j < n; j++) {
        dp[0][j] = (obstacleGrid[0][j] == 1) ? 0 : dp[0][j-1];
    }

    // 动态规划计算
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0; // 有障碍物，路径数为 0
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }

    // 返回右下角的路径数
    return dp[m-1][n-1];
}

int main() {
    int grid[3][3] = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
    int* gridPointer[3] = {grid[0], grid[1], grid[2]};
    int cols = 3;
    printf("不同路径的数量: %d\n", uniquePathsWithObstacles(gridPointer, 3, &cols));
    return 0;
}