LeetCode m×n矩阵不同路径问题：一维DP解法解析求助

嘿，我来帮你拆解这个一维DP的解法——它其实就是你已经理解的二维DP的空间优化版本，核心思路是复用数组空间，把O(mn)的空间复杂度降到O(min(m,n))，咱们一步步理清楚：

先回顾你熟悉的二维DP核心 #

你已经知道二维DP的逻辑：

• 用count[i][j]存储从左上角到(i,j)的路径数
• 初始化第一行和第一列为1（只能一直往右/往下走，只有1种路径）
• 状态转移：count[i][j] = count[i-1][j] + count[i][j-1]——到达(i,j)的路径数等于从上方来的路径数加从左方来的路径数

为什么能压缩成一维数组？ #

仔细看状态转移方程：计算count[i][j]时，我们只需要两个值：

1. 上一行同一列的值：count[i-1][j]（还没被覆盖的旧值）
2. 当前行前一列的值：count[i][j-1]（刚计算出来的新值）

所以完全不需要保留整个二维数组，只用一个一维数组dp就能复用空间，每次迭代覆盖更新当前行的结果。

逐行解析一维DP代码 #

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    dp[0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

1. 初始化阶段 #

int[] dp = new int[n]; dp[0] = 1;

• 初始时dp数组除了dp[0]为1，其余都是0。这相当于我们先初始化了二维DP里的第0列（所有行的第0列都是1），同时为后续计算第一行做准备。

2. 外层循环（遍历每一行） #

for (int i = 0; i < m; i++)

• 这里的i代表当前处理的是第i行，从第0行到第m-1行。

3. 内层循环（遍历当前行的列） #

for (int j = 1; j < n; j++)

• 从第1列开始遍历（第0列始终是1，不需要更新），核心逻辑在dp[j] += dp[j - 1]，咱们用m=3，n=3的例子拆解：

第一次外层循环（i=0，处理第0行）

初始dp = [1, 0, 0]

• j=1：dp[1] = 0 + dp[0] = 1 → dp = [1,1,0]
• j=2：dp[2] = 0 + dp[1] = 1 → dp = [1,1,1]
  这时候dp数组就是二维DP里的第0行，全1，符合初始化规则。

第二次外层循环（i=1，处理第1行）

初始dp = [1,1,1]（上一行的结果）

• j=1：dp[1] = 1（上一行的j=1值） + dp[0]（当前行j-1=0的值）= 2 → dp = [1,2,1]
• j=2：dp[2] = 1（上一行的j=2值） + dp[1]（当前行刚更新的j=1的值）=3 → dp = [1,2,3]
  这时候dp数组对应二维DP里的第1行：count[1][0]=1，count[1][1]=2，count[1][2]=3，完全一致。

第三次外层循环（i=2，处理第2行）

初始dp = [1,2,3]（上一行的结果）

• j=1：dp[1] =2 +1=3 → dp = [1,3,3]
• j=2：dp[2] =3 +3=6 → dp = [1,3,6]
  最终返回dp[2]=6，这就是3×3矩阵的正确路径数。

核心总结 #

dp[j] += dp[j-1]这句话的本质是：

更新前的dp[j]是上一行j列的路径数，dp[j-1]是当前行j-1列的路径数，两者相加就是当前行j列的路径数，完美对应二维DP的状态转移方程。

这种优化方式在很多DP问题里都能用，只要状态转移只依赖前一行或前一列的值，就可以考虑压缩空间～

内容的提问来源于stack exchange，提问作者Nicky