LeetCode 63. 不同路径 II

Categories:

题目描述
思路分析
1. 解法一：二维动态规划（推荐）
2. 解法二：一维 DP 空间优化
相似题目

题目描述

✅ 63. 不同路径 II

思路分析

解法一：二维动态规划（推荐）

核心思路：

定义 dp[i][j] 表示从起点 (0, 0) 到达 (i, j) 的不同路径数。

若 obstacleGrid[i][j] == 1，该格子有障碍，dp[i][j] = 0。

否则，dp[i][j] = dp[i-1][j] + dp[i][j-1]（只能从上方或左方到达）。

初始化：起点无障碍则 dp[0][0] = 1；第一行和第一列遇到障碍后，后续格子均为 0。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为网格的行数和列数。

空间复杂度：O(m × n)，使用二维 dp 数组。

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

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

        // 初始化第一列：遇到障碍后全部为 0
        for (int i = 1; i < m; i++) {
            dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0];
        }

        // 初始化第一行：遇到障碍后全部为 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;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	m := len(obstacleGrid)
	n := len(obstacleGrid[0])
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	// 起点有障碍，直接返回 0
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	dp[0][0] = 1

	// 初始化第一列：遇到障碍后全部为 0
	for i := 1; i < m; i++ {
		if obstacleGrid[i][0] == 1 {
			dp[i][0] = 0
		} else {
			dp[i][0] = dp[i-1][0]
		}
	}

	// 初始化第一行：遇到障碍后全部为 0
	for j := 1; j < n; j++ {
		if obstacleGrid[0][j] == 1 {
			dp[0][j] = 0
		} else {
			dp[0][j] = dp[0][j-1]
		}
	}

	// 状态转移
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if obstacleGrid[i][j] == 1 {
				dp[i][j] = 0
			} else {
				dp[i][j] = dp[i-1][j] + dp[i][j-1]
			}
		}
	}

	return dp[m-1][n-1]
}

解法二：一维 DP 空间优化

核心思路：

观察状态转移 dp[i][j] = dp[i-1][j] + dp[i][j-1]，第 i 行只依赖第 i-1 行的同列值和当前行左侧值。

用一维数组 dp[j] 滚动更新：dp[j] = dp[j] + dp[j-1]，其中 dp[j] 代表上一行同列，dp[j-1] 代表当前行左侧。

遇到障碍时将 dp[j] 置为 0，阻断路径传播。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为网格的行数和列数。

空间复杂度：O(n)，只使用长度为 n 的一维滚动数组。

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid[0].length;
        int[] dp = new int[n];

        // 起点无障碍则初始化为 1
        dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;

        for (int[] row : obstacleGrid) {
            for (int j = 0; j < n; j++) {
                // 当前格子有障碍，路径数置为 0
                if (row[j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                    // dp[j] 保留上一行同列值，加上左侧值完成滚动更新
                    dp[j] += dp[j - 1];
                }
            }
        }

        return dp[n - 1];
    }
}

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	n := len(obstacleGrid[0])
	dp := make([]int, n)

	// 起点无障碍则初始化为 1
	if obstacleGrid[0][0] == 0 {
		dp[0] = 1
	}

	for _, row := range obstacleGrid {
		for j := 0; j < n; j++ {
			// 当前格子有障碍，路径数置为 0
			if row[j] == 1 {
				dp[j] = 0
			} else if j > 0 {
				// dp[j] 保留上一行同列值，加上左侧值完成滚动更新
				dp[j] += dp[j-1]
			}
		}
	}

	return dp[n-1]
}

相似题目

题目	难度	考察点
62. 不同路径	中等	动态规划
64. 最小路径和	中等	动态规划
980. 不同路径 III	困难	回溯、状态压缩
120. 三角形最小路径和	中等	动态规划
931. 下降路径最小和	中等	动态规划
1289. 下降路径最小和 II	困难	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/30979546