当前位置：首页 > web >正文

【LeetCode 热题 100】62. 不同路径——（解法二）递推

web 2025/8/30 8:44:46

Problem: 62. 不同路径

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(m * n)
- 空间复杂度：O(m * n)

整体思路

这段代码同样旨在解决 “不同路径” 问题，但它采用的是一种 自底向上（Bottom-Up）的动态规划 方法，也称为 迭代法 或 制表法 (Tabulation)。这种方法通过构建一个DP表（dp 二维数组），从起点开始，逐步计算出到达每个格子的路径数，最终得到终点的答案。

该实现通过巧妙地增加DP数组的维度（使用 m+1 和 n+1），将边界条件的处理融入到统一的状态转移方程中，使得代码非常简洁。

状态定义与索引映射：
- 算法定义了一个二维DP数组 dp，大小为 (m+1) x (n+1)。
- dp[i][j] 的含义是：从起点 (1, 1)（对应 nums[0][0]）到达网格中的点 (i, j) 的不同路径数。
- 这是一个索引偏移的技巧。dp 数组的索引 (i, j) 对应了 m x n 网格中的索引 (i-1, j-1)。这样做的好处是，dp 数组的第0行和第0列可以作为天然的边界，避免了在循环中进行 i>0 或 j>0 的判断。
基础情况 (Base Case)：
- dp[1][1] = 1：这是整个DP计算的起点。它表示从起点到达起点 (1,1)（即 grid[0][0]）只有1条路径（原地不动）。
- dp 数组的其他元素默认初始化为 0。dp 的第0行和第0列全为0，这恰好满足我们的边界条件：无法从网格外部进入，路径数为0。
状态转移 (State Transition)：
- 算法使用两层嵌套循环来填充DP表。循环变量 i 和 j 对应的是 m x n 网格的索引。
- 在循环的每一步，计算 dp[i+1][j+1] 的值。
- 状态转移方程是 dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]。
- 我们来解析这个方程：
  - 要到达 dp 中的点 (i+1, j+1)（对应 grid[i][j]），只能从其左边的点 (i+1, j)（对应 grid[i][j-1]）或上边的点 (i, j+1)（对应 grid[i-1][j]）过来。
  - 因此，到达 (i+1, j+1) 的总路径数，就是到达这两个点的路径数之和。
  - 当 i=0 或 j=0 时，例如计算 dp[1][j+1]，方程变为 dp[1][j+1] = dp[1][j] + dp[0][j+1]。因为 dp[0][j+1] 总是0，所以 dp[1][j+1] = dp[1][j]，这正确地表示了第一行所有格子的路径数都为1。对第一列同理。
返回结果：
- 当所有循环结束后，dp 数组已经完全填充。我们需要的最终答案，即到达终点 grid[m-1][n-1] 的路径数，就存储在 dp[m][n] 中。

完整代码

class Solution {/*** 计算从 m x n 网格的左上角到右下角的不同路径数。* @param m 网格的行数* @param n 网格的列数* @return 不同的路径总数*/public int uniquePaths(int m, int n) {// dp: 动态规划数组。dp[i][j] 表示从起点到网格 (i-1, j-1) 的路径数。// 使用 m+1, n+1 的大小是为了用第0行和第0列作为边界，简化代码。int[][] dp = new int[m + 1][n + 1];// 基础情况：到达起点 (0,0) 的路径数是 1。// 在我们的 dp 表中，这对应 dp[1][1]。dp[1][1] = 1;// i 和 j 是原始网格的索引 (0-based)for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 跳过我们已经设置的起点if (i == 0 && j == 0)continue;// 状态转移方程：// 到达网格 (i, j) 的路径数，等于到达其上方格子 (i-1, j)// 和左方格子 (i, j-1) 的路径数之和。// 在 dp 表中，这对应于：// dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1];}}// 最终答案是到达网格 (m-1, n-1) 的路径数，对应 dp[m][n]。return dp[m][n];}
}

时空复杂度

时间复杂度：O(m * n)

循环结构：算法使用了两层嵌套的 for 循环。
- 外层循环从 i = 0 运行到 m-1，执行 m 次。
- 内层循环从 j = 0 运行到 n-1，执行 n 次。
计算依据：
- 总的操作次数（主要是加法和赋值）是内外层循环次数的乘积，即 m * n。