不同路径

一个机器人位于一个 m x n 网格的左上角。

机器人每次只能向下或者向右移动一步。

机器人试图达到网格的右下角。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 10^9

解法一（二维动态规划）：

class Solution {
public:
    int uniquePaths(int m, int n) {
        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];
    }
};

解法二（一维滚动数组优化）：

class Solution {
public:
    int uniquePaths(int m, int n) {
        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];
    }
};

核心思想

这题是一个典型的动态规划问题。

机器人每次只能向右或者向下移动。

所以对于网格中的某个位置 (i, j)，它只可能从两个位置走过来：

• 从上方 (i - 1, j) 向下走一步
• 从左方 (i, j - 1) 向右走一步

除此之外没有其它方式。

这题最关键的观察是：

到达当前位置的路径数，等于到达它上方位置的路径数，加上到达它左方位置的路径数。

因此只要从左上角开始，按行或按列逐步计算，就能得到右下角的答案。

状态定义

定义：

dp[i][j] 表示从左上角走到第 i 行第 j 列位置的不同路径数。

这里下标从 0 开始。

题目要求的答案就是：

dp[m - 1][n - 1]

也就是右下角位置的路径数。

递推公式推导

考虑位置 (i, j)。

因为机器人只能向右或向下走，所以想进入 (i, j)，最后一步只有两种可能。

1. 从上方走下来

如果最后一步是从 (i - 1, j) 向下走，那么路径数是：

dp[i - 1][j]

2. 从左方走过来

如果最后一步是从 (i, j - 1) 向右走，那么路径数是：

dp[i][j - 1]

这两类路径的最后一步来源不同，不会重复。

所以：

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

代码中写成：

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

边界情况

第一行的所有位置都只能从左边一路向右走过来。

所以第一行每个位置只有 1 条路径：

dp[0][j] = 1

第一列的所有位置都只能从上边一路向下走过来。

所以第一列每个位置也只有 1 条路径：

dp[i][0] = 1

因此代码中可以直接初始化：

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

如果 m = 1 或 n = 1，机器人只能沿着唯一的一行或一列走，答案也是 1。

这个初始化也能自然处理。

为什么可以按行递推

计算 dp[i][j] 时，只依赖：

• 上方的 dp[i - 1][j]
• 左方的 dp[i][j - 1]

如果我们从上到下、从左到右遍历：

• dp[i - 1][j] 已经在上一行算好
• dp[i][j - 1] 已经在当前行左边算好

所以当前位置可以直接由已知状态推出。

这就是动态规划的计算顺序。

解法二：一维滚动数组优化

二维动态规划中，计算当前行时，只需要用到：

• 上一行同一列的值
• 当前行左一列的值

所以可以用一维数组 dp[j] 表示当前处理到这一行时，到达第 j 列的路径数。

在更新前：

dp[j] 表示上一行第 j 列的路径数。

dp[j - 1] 表示当前行第 j - 1 列的路径数。

所以更新公式是：

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

其中：

• 原来的 dp[j] 相当于二维里的 dp[i - 1][j]
• dp[j - 1] 相当于二维里的 dp[i][j - 1]

这就把空间复杂度从 O(mn) 降到了 O(n)。

正确性证明

我们证明：动态规划算法返回的结果等于从左上角到右下角的不同路径数。

结论 1：第一行和第一列的初始化正确

对于第一行，机器人只能一直向右走。

所以到达第一行任意位置都只有 1 条路径。

对于第一列，机器人只能一直向下走。

所以到达第一列任意位置也只有 1 条路径。

因此初始化第一行和第一列为 1 是正确的。

结论 2：递推公式正确计算了每个内部位置的路径数

对于内部位置 (i, j)，最后一步只能来自上方 (i - 1, j) 或左方 (i, j - 1)。

从上方来的路径共有 dp[i - 1][j] 条。

从左方来的路径共有 dp[i][j - 1] 条。

这两类路径最后一步不同，因此不会重复。

同时，所有到达 (i, j) 的合法路径都必须属于这两类之一，因此不会遗漏。

所以：

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

正确。

结论 3：按行遍历时，递推所需状态已经计算完成

当计算 dp[i][j] 时，上一行的 dp[i - 1][j] 已经计算完成。

当前行左侧的 dp[i][j - 1] 也已经计算完成。

所以每个状态都能由已知状态正确推出。

结论 4：一维滚动数组与二维动态规划等价

一维数组更新时：

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

更新前的 dp[j] 表示上一行同一列的路径数。

更新后的 dp[j - 1] 表示当前行左一列的路径数。

这与二维递推公式：

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

完全一致。

因此一维滚动数组不会改变计算结果。

得出结论

由结论 1 可知，边界初始化正确。

由结论 2 可知，状态转移正确。

由结论 3 可知，计算顺序正确。

由结论 4 可知，一维优化与二维动态规划等价。

因此算法返回的 dp[m - 1][n - 1] 或 dp[n - 1] 就是不同路径总数。

举例理解

以：

m = 3, n = 3

为例。

初始化第一行和第一列：

1 1 1
1 ? ?
1 ? ?

计算内部位置：

• dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
• dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
• dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
• dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6

最终表格是：

1 1 1
1 2 3
1 3 6

所以答案是：

6

复杂度分析

解法一

需要计算 m * n 个位置。

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

解法二

同样需要计算每个位置一次。

一维数组长度为 n。

• 时间复杂度：O(mn)
• 空间复杂度：O(n)

解法二空间更优，是更推荐的写法。