不同路径 II

约 1747 字大约 6 分钟

2025-01-13

⭐ 题目日期：

字节 - 2024/12/10

🌳 题目描述：

给定一个二维整数数组 grid，一个机器人初始位于 grid[0][0]，需要移动到 grid[m - 1][n - 1]，机器人每次只能向下或者向右移动一步，且移动路径中不能包含障碍物。网格中存在的障碍物，用 1 表示，空位置用 0 表示，返回机器人能够到达目的的不同路径的数量，注意：移动路径中不能包含障碍物！

示例1：

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

🕵🏽 面试评估：

这道题主要考察候选人能否通过理解动态规划和状态转移的核心思想，成功地将不同路径问题拆解为多个子问题。每个子问题代表了从起点到当前位置的路径数，并通过机器人只能向下和向右运动，推理出可行走的路径数需要通过上方或左方的路径数累加而来，从而得出状态转移方程，最终计算出从起点到终点的所有可能路径

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

这道题的要求是从 grid[0][0]，需要移动到 grid[m - 1][n - 1]，那么我们可以定义一个二维数组 dp[i][j] 来表示从 (0,0) 到 (i,j) 位置的不同路径的数量。

动态规划的状态转移方程为：

如果 grid[i][j] == 1，则 dp[i][j] = 0（障碍物位置不能到达）。
否则，dp[i][j] = dp[i-1][j] + dp[i][j-1]，即当前位置的路径数等于从上方和左方到达该位置的路径数之和。

随后需要初始化第一行和第一列：题目所给的 grid 中，会有障碍物的出现，那么当遇到障碍物的时候，因为后面的路都没法走，所以后面的路径数为 0；如果该位置没有障碍物，且没有障碍物阻挡之前的路径，则将路径数设置为 1。

最终返回右下角 dp[m-1][n-1] 的值，表示从左上角到右下角的不同路径数量

以案例 1 为例，最后得出的 dp 数组为：

1	0	0
1	1	1
1	2	3

所以最终返回 3

空间优化思路：dp 数组的计算只需要用到dp[i-1][j]（上一行的值）和 dp[i][j-1]（当前行左边的值）。因此，只需要维护一维数组来记录当前行的路径数。

💻代码：

Java

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;

    // 如果起点或者终点有障碍物，直接返回
    if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
        return 0;
    }

    int[][] dp = new int[m][n];
    // 初始化第一列
    for (int i = 0; i < m; i++) {
        if (obstacleGrid[i][0] == 1) {
            break;
        }
        dp[i][0] = 1;
    }

    // 初始化第一行
    for (int j = 0; j < n; j++) {
        if (obstacleGrid[0][j] == 1) {
            break;
        }
        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];
}

Python

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 = [[0] * n for _ in range(m)]  # 初始化 DP 数组

    # 初始化第一列
    for i in range(m):
        if obstacleGrid[i][0] == 1:
            break
        dp[i][0] = 1
  
    # 初始化第一行
    for j in range(n):
        if obstacleGrid[0][j] == 1:
            break
        dp[0][j] = 1

    for i in range(1, m):
        for j in range(1, n):
            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]

C++

#include <vector>
using namespace std;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();

        // 如果起点或者终点有障碍物，直接返回
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }

        vector<vector<int>> dp(m, vector<int>(n, 0));

        // 初始化第一列
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }

        // 初始化第一行
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                break;
            }
            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];
    }
};

优化后的代码：

Java

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;

    // 如果起点或者终点有障碍物，直接返回
    if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
        return 0;
    }

    int[] dp = new int[n];
    dp[0] = 1; // 起点初始化为 1

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0; // 如果当前位置是障碍物，路径数为 0
            } else if (j > 0) {
                dp[j] += dp[j - 1]; // 路径数为来自上方和左方的路径数之和
            }
        }
    }

    return dp[n - 1]; 
}

Python

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])

        # 如果起点或者终点有障碍物，直接返回 0
        if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1:
            return 0

        dp = [0] * n
        dp[0] = 1  # 起点初始化为 1

        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[j] = 0  # 如果当前位置是障碍物，路径数为 0
                elif j > 0:
                    dp[j] += dp[j - 1]  # 路径数为来自上方和左方的路径数之和

        return dp[-1]

C++

#include <vector>
using namespace std;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();

        // 如果起点或者终点有障碍物，直接返回 0
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }

        vector<int> dp(n, 0);
        dp[0] = 1; // 起点初始化为 1

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0; // 如果当前位置是障碍物，路径数为 0
                } else if (j > 0) {
                    dp[j] += dp[j - 1]; // 路径数为来自上方和左方的路径数之和
                }
            }
        }

        return dp[n - 1];
    }
};

🚵🏻复杂度分析：

时间复杂度: O(m * n)，其中 m 为二维数组的行数，n 为二维数组的列数

空间复杂度: O(n)，优化后只使用一个一维数组来存储，n 为二维数组的列数，优化前为 O(m * n)，其中 m 为二维数组的行数，n 为二维数组的列数

🔬在线评测(Online Judge):

题目链接