力扣第63题-不同路径Ⅱ


1.拿到题目一开始的思路是进行递归穷举的深度搜索算法,因为机器人只能向下或者向右走,即只能更靠近目标点,所以可以先假定机器人先向右走到最远,然后找出从该点到目标值的路径数,遇到不能走的地方可以回退,找完本列就继续找前一列,直到遍历完所有列就可以得出路径数。代码如下:
1. // DFS 暴力搜索所有路径
2. int dfs(int** grid, int i, int j, int row, int col) {
3. // 越界 或 遇到障碍物 → 此路不通
4. if (i >= row || j >= col || grid[i][j] == 1)
5. return 0;
6.
7. // 走到终点 → 找到一条有效路径
8. if (i == row-1 && j == col-1)
9. return 1;
10.
11. // 先向右走到底,再向下走
12. // 总路径 = 向右走的路径数 + 向下走的路径数
13. return dfs(grid, i, j+1, row, col) + dfs(grid, i+1, j, row, col);
14. }
15.
16. int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
17. int row = obstacleGridSize;
18. int col = *obstacleGridColSize;
19. return dfs(obstacleGrid, 0, 0, row, col);
20. }
但这样的话时间复杂度为O(2^(m+n)),会超时,并不能使用。
2.最优解应该是使用动态规划,由题目的条件可以得出想要到达某一个点,只能从上面或者左面走到,那么能到达该点的路径数就等于它上面格子和左面格子的路径数。如果该格子有障碍物,那就说明该格子的可达路径数为0。于是可以写出如下代码:
1. /**
2. * 不同路径 II(带障碍物)- 标准二维动态规划解法
3. * 机器人从左上角 (0,0) 出发,只能向右 / 向下走
4. * 障碍物无法通过,计算到达右下角的总路径数
5. */
6. int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize) {
7. // 获取矩阵维度:rowMax = 行数,colMax = 列数
8. int rowMax = obstacleGridSize;
9. int colMax = *obstacleGridColSize;
10.
11. // 定义二维DP数组:nums[i][j] 表示 到达 (i,j) 位置的总路径数
12. int nums[rowMax][colMax];
13.
14. // ====================== 1. 初始化起点 ======================
15. // 如果起点就是障碍物,直接返回 0 条路径
16. if (obstacleGrid[0][0] == 1){
17. return 0;
18. } else {
19. // 起点无障碍:到达起点的路径数 = 1(只有站在原地这一种)
20. nums[0][0] = 1;
21. }
22.
23. // ====================== 2. 遍历填充DP数组 ======================
24. // 逐行遍历
25. for (int i = 0; i < rowMax; i++){
26. // 逐列遍历
27. for (int j = 0; j < colMax; j++){
28. // 跳过起点:起点已经初始化,不需要再计算
29. if (i == 0 && j == 0){
30. continue;
31. }
32.
33. // ====================== 障碍物处理 ======================
34. // 如果当前位置是障碍物,到达这里的路径数 = 0
35. if (obstacleGrid[i][j] == 1){
36. nums[i][j] = 0;
37. continue;
38. }
39.
40. // ====================== 状态转移(核心) ======================
41. // 情况1:位于第一行(只能从左边的格子向右走过来)
42. if (i == 0){
43. nums[i][j] = nums[i][j – 1];
44. }
45. // 情况2:位于第一列(只能从上面的格子向下走过来)
46. else if (j == 0){
47. nums[i][j] = nums[i – 1][j];
48. }
49. // 情况3:普通位置(可以从左边 或 上边走过来,路径数相加)
50. else {
51. nums[i][j] = nums[i][j – 1] + nums[i – 1][j];
52. }
53. }
54. }
55.
56. // ====================== 3. 返回终点结果 ======================
57. // 终点坐标:右下角 (rowMax-1, colMax-1)
58. return nums[rowMax – 1][colMax – 1];
59. }
该算法的时间复杂度为O(rowMax * colMax),即遍历一遍完整矩阵,已是最优解。
3.官方的代码更为巧妙,没有使用二维数组,而是使用了一维数组。这样的话每一行都会对该数组进行覆写,而该数组本身就储存着上一行的可达路径数,所以每次都执行f[j] += f[j – 1];即可得出该格的可达路径数。完整代码如下:
1. // 函数作用:返回从左上角到右下角的路径数量(带障碍物)
2. int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize,
3. int* obstacleGridColSize) {
4. // n = 矩阵的行数
5. // m = 矩阵的列数
6. int n = obstacleGridSize, m = obstacleGridColSize[0];
7.
8. // —————————————————— 核心:一维 DP 数组 ——————————————————
9. // f[j] 表示:到达【当前行、第 j 列】这个位置,有多少条路径
10. int f[m];
11. // 把数组全部初始化为 0(一开始所有位置都 0 条路)
12. memset(f, 0, sizeof(f));
13.
14. // —————————————————— 初始化起点 ——————————————————
15. // 如果起点 (0,0) 没有障碍物 → 路径数 = 1
16. // 如果起点是障碍物 → 路径数 = 0
17. f[0] = (obstacleGrid[0][0] == 0);
18.
19. // —————————————————— 遍历整个矩阵 ——————————————————
20. // 外层循环:一行一行走 i
21. for (int i = 0; i < n; ++i) {
22. // 内层循环:一列一列走 j
23. for (int j = 0; j < m; ++j) {
24.
25. // —————— 情况1:当前格子是障碍物 ——————
26. if (obstacleGrid[i][j] == 1) {
27. f[j] = 0; // 不能走 → 路径数 = 0
28. continue; // 跳过,不用再计算
29. }
30.
31. // —————— 情况2:当前格子可以走 ——————
32. // 看看能不能从【左边】走过来
33. if (j – 1 >= 0) {
34. f[j] += f[j – 1];
35. }
36. }
37. }
38.
39. // 最后返回终点 f[m-1] 的值 = 总路径数
40. return f[m – 1];
41. }
进行数组降维优化后,空间复杂度从O(mn)降为了O(m)。
力扣第64题-最小路径和

1.本题是力扣第63题的变种,同样是要使用动态规划来解答。可以继续使用第63题使用一维数组来储存格子对应值的优化,这次需要储存的是到达本格的最小路径和。在遍历矩阵的时候需要分三类讨论,即列数为0、行数为0以及其他情况,完整代码如下:
1. int minPathSum(int** grid, int gridSize, int* gridColSize) {
2. // 矩阵行数
3. int rowMax = gridSize;
4. // 矩阵列数
5. int colMax = *gridColSize;
6.
7. // 一维DP数组:nums[j] 表示 到达当前行第j列 的最小路径和
8. int nums[colMax];
9. // 初始化数组全部为 0(安全初始化)
10. memset(nums, 0, sizeof(nums));
11.
12. // 逐行遍历整个矩阵
13. for (int i = 0; i < rowMax; i++){
14. // 逐列遍历当前行
15. for (int j = 0; j < colMax; j++){
16.
17. // ====================== 情况1:第一列 ======================
18. // 只能从 正上方 走下来
19. // 所以直接累加当前格子的值
20. if (j == 0){
21. nums[j] += grid[i][j];
22. }
23.
24. // ====================== 情况2:第一行 ======================
25. // 只能从 左边 走过来
26. // 所以 = 左边的最小和 + 当前值
27. else if (i == 0) {
28. nums[j] = nums[j – 1] + grid[i][j];
29. }
30.
31. // ====================== 情况3:普通位置(最核心) ======================
32. // 可以从 上方 或 左方 过来
33. // 取 更小的那个值 + 当前格子的值
34. else {
35. nums[j] = (nums[j] < nums[j – 1] ? nums[j] : nums[j – 1]) + grid[i][j];
36. }
37. }
38. }
39.
40. // 最后返回终点:右下角的最小路径和
41. return nums[colMax – 1];
42. }
该算法的时间复杂度为O(rowMax * colMax),空间复杂度为O(colMax),均已是最优。

![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)
![打卡信奥刷题(3678)用C++实现信奥题 P12274 [蓝桥杯 2024 国 Python B] 设计-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108053830-6af00ad6bdf8d-220x150.png)

