AlgoViz Lab交互式算法学习Algorithms first
不同路径 II · 交互式算法学习
有障碍时计算从左上到右下的不同路径数。
#63 · 多维动态规划
不同路径 II
Unique Paths II
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]状态表3 个关键状态
步骤 1第一行路径数 [1,1,1]。
dp0120
0
0
0
10
1
0
20
0
0
当前状态转移来源
推荐
一维路径计数 DP
时间
O(mn)空间 O(n)dp[c] 保留从上方来的路径；非障碍格再加左侧 dp[c-1]。
1function uniquePathsWithObstacles(g) {2 const dp = Array(g[0].length).fill(0);3 dp[0] = 1;4 for (const row of g)5 for (let c = 0; c < row.length; c++)6 if (row[c]) dp[c] = 0;7 else if (c) dp[c] += dp[c - 1];8 return dp.at(-1);9}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 private Integer[][] f;3 private int[][] obstacleGrid;4 private int m;5 private int n;6 7 public int uniquePathsWithObstacles(int[][] obstacleGrid) {8 m = obstacleGrid.length;9 n = obstacleGrid[0].length;10 this.obstacleGrid = obstacleGrid;11 f = new Integer[m][n];12 return dfs(0, 0);13 }14 15 private int dfs(int i, int j) {16 if (i >= m || j >= n || obstacleGrid[i][j] == 1) {17 return 0;18 }19 if (i == m - 1 && j == n - 1) {20 return 1;21 }22 if (f[i][j] == null) {23 f[i][j] = dfs(i + 1, j) + dfs(i, j + 1);24 }25 return f[i][j];26 }27}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
不同路径 II · 解法对比
有障碍时计算从左上到右下的不同路径数。
- 测试用例
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]- 题目分类
- 多维动态规划
- 解法对比
- 2
带障碍递归
遇到障碍返回 0，否则路径数是右与下之和。
- 时间
指数级- 空间
O(m+n)
一维路径计数 DP
dp[c] 保留从上方来的路径；非障碍格再加左侧 dp[c-1]。
- 时间
O(mn)- 空间
O(n)