一、二维 DP（基础版本）

1. 完整代码（精简注释）

class Solution {
public:
    int uniquePaths(int m, int n) {
        // dp[i][j]：到达位置 (i,j) 的路径数
        vector<vector<int>> dp(m, vector<int>(n, 1));

        // 从第二行、第二列开始遍历
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 当前路径数 = 上方路径数 + 左方路径数
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        // 返回右下角的路径数
        return dp[m-1][n-1];
    }
};

2. 动态规划五步总结

（1）确定 DP 数组及其含义

dp[i][j] 表示从左上角 (0,0) 出发，到达位置 (i,j) 的不同路径数量。

（2）确定递推公式

由于机器人只能向右或者向下移动，因此到达当前位置只有两种方式：

• 从上方 (i-1,j) 向下移动。

• 从左方 (i,j-1) 向右移动。

因此：

dp[i][j] = dp[i-1][j] + dp[i][j-1];

即：当前位置的路径数 = 上方路径数 + 左方路径数。

（3）DP 数组初始化

vector<vector<int>> dp(m, vector<int>(n, 1));

将所有元素初始化为 1。

原因：

• 第一行只能一直向右走，因此路径数为 1。

• 第一列只能一直向下走，因此路径数为 1。

• 其余位置会通过递推公式重新计算。

（4）确定遍历顺序

for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
}

从上到下、从左到右遍历。

因为计算当前位置时，需要使用上方和左方已经计算好的结果。

（5）举例推导 DP 数组

假设：

m = 3;
n = 4;

最终 DP 数组：

1  1  1   1
1  2  3   4
1  3  6  10

例如：

dp[1][1] = dp[0][1] + dp[1][0] = 2;
dp[1][2] = dp[0][2] + dp[1][1] = 3;
dp[2][2] = dp[1][2] + dp[2][1] = 6;
dp[2][3] = dp[1][3] + dp[2][2] = 10;

最终返回 dp[2][3] = 10。

3. 复杂度分析

• 时间复杂度：O(m × n)，需要遍历整个网格。

• 空间复杂度：O(m × n)，需要保存二维 DP 数组。

二、一维 DP（空间优化版本）

1. 完整代码（精简注释）

class Solution {
public:
    int uniquePaths(int m, int n) {
        // dp[j]：当前行第 j 列的路径数
        vector<int> dp(n, 1);

        // 从第二行开始遍历
        for (int i = 1; i < m; i++) {
            // 从第二列开始更新
            for (int j = 1; j < n; j++) {
                // 当前路径数 = 上方路径数 + 左方路径数
                dp[j] = dp[j] + dp[j-1];
            }
        }

        // 返回右下角的路径数
        return dp[n-1];
    }
};

2. 动态规划五步总结

（1）确定 DP 数组及其含义

dp[j] 表示当前处理到的行中，第 j 列位置的路径数量。

注意：一维 DP 数组会随着外层循环不断更新，代表不同的行。

（2）确定递推公式

二维 DP 的递推公式：

dp[i][j] = dp[i-1][j] + dp[i][j-1];

压缩成一维后：

dp[j] = dp[j] + dp[j-1];

为什么可以这样写？

• 更新前的 dp[j]：表示上一行同一列的路径数，即上方。

• 更新后的 dp[j-1]：表示当前行左边一列的路径数，即左方。

因此，两者相加就是当前格子的路径数。

（3）DP 数组初始化

vector<int> dp(n, 1);

初始化为第一行的路径数。

因为第一行所有位置都只能一直向右移动，所以路径数都是 1。

（4）确定遍历顺序

for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        dp[j] += dp[j-1];
    }
}

• 外层从第二行开始遍历。

• 内层从第二列开始，从左往右更新。

为什么必须从左往右？

因为计算当前 dp[j] 时，需要使用已经更新的 dp[j-1]，它表示当前行左边位置的路径数。

（5）举例推导 DP 数组

假设：

m = 3;
n = 4;

初始化：

dp = [1, 1, 1, 1]

处理第二行：

dp[1] = 1 + 1 = 2;
dp[2] = 1 + 2 = 3;
dp[3] = 1 + 3 = 4;

得到：

dp = [1, 2, 3, 4]

处理第三行：

dp[1] = 2 + 1 = 3;
dp[2] = 3 + 3 = 6;
dp[3] = 4 + 6 = 10;

得到：

dp = [1, 3, 6, 10]

最终返回：

return dp[n-1];  // 10

3. 复杂度分析

• 时间复杂度：O(m × n)，需要遍历整个网格。

• 空间复杂度：O(n)，只需要保存一行的 DP 状态。

三、二维 DP 与一维 DP 对比

对比项	二维 DP	一维 DP
DP 定义	dp[i][j]	dp[j]
递推公式	dp[i-1][j]+dp[i][j-1]	dp[j]+dp[j-1]
初始化	dp(m, vector<int>(n,1))	dp(n,1)
遍历顺序	从上到下、从左到右	从上到下、从左到右
时间复杂度	O(m × n)	O(m × n)
空间复杂度	O(m × n)	O(n)

四、核心易错点

1. 为什么二维 DP 可以压缩成一维？

因为计算当前位置时，只需要上方和左方的路径数，不需要保存整个二维数组。

2. 为什么一维 DP 必须从左往右更新？

因为 dp[j-1] 必须是当前行已经更新过的值，才能正确表示左方路径数。

3. 为什么循环从 i=1、j=1 开始？

因为第一行和第一列都只有一条路径，已经初始化为 1，不需要再次计算。

4. 为什么二维 DP 返回 dp[m-1][n-1]，一维 DP 返回 dp[n-1]？

二维 DP 保存整个网格，所以右下角对应 dp[m-1][n-1]。

一维 DP 只保存当前行，遍历到最后一行后，dp[n-1] 就是右下角的路径数。

五、最终总结

这道题的核心思想是：

当前位置的路径数 = 上方位置的路径数 + 左方位置的路径数。

二维 DP：

dp[i][j] = dp[i-1][j] + dp[i][j-1];

一维 DP：

dp[j] = dp[j] + dp[j-1];

二者的本质完全相同，只是存储状态的方式不同。

• 二维 DP：保存整个网格的路径数，更容易理解。

• 一维 DP：只保存一行的路径数，利用上一行和当前行的状态进行更新，节省空间。

记忆：先通过二维 DP 理解状态转移，再根据当前状态只依赖上方和左方的特点，将二维 DP 压缩成一维 DP。