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

Problem: 62. 不同路径

整体思路

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

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

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 的判断。

2. 基础情况 (Base Case)：

   • dp[1][1] = 1：这是整个DP计算的起点。它表示从起点到达起点 (1,1)（即 grid[0][0]）只有1条路径（原地不动）。
   • dp 数组的其他元素默认初始化为 0。dp 的第0行和第0列全为0，这恰好满足我们的边界条件：无法从网格外部进入，路径数为0。

3. 状态转移 (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。对第一列同理。

4. 返回结果：

   • 当所有循环结束后，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)

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

综合分析：
算法的时间复杂度为 O(m * n)。

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

1. 主要存储开销：算法创建了一个名为 dp 的二维整型数组来存储动态规划的所有中间状态。
2. 空间大小：该数组的大小是 (m + 1) * (n + 1)。

综合分析：
算法所需的额外空间主要由 dp 数组决定，其空间复杂度为 O(m * n)。