一个机器人位于一个 m x n 网格的左上角(坐标 (0， 0))。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(坐标 (m - 1， n - 1))。

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

示例 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⁹

方案一：递归

• 每次有两种选择，向下走或者向右走
• 递归退出条件：走到坐标为 (m - 1, n - 1)的位置

int uniquePaths(int m, int n) {
    int res = 0;
    helper(m - 1, n - 1, 0, 0, res);
    return res;
}
void helper(int m, int n, int row, int col, int &res) {
    if (row == m && col == n) {
        res++;
        return;
    }
    if (row < m)
        helper(m, n, row + 1, col, res);
    if (col < n)
        helper(m, n, row, col + 1, res);
}

方案二：动态规划

• dp[i][j] 表示到达坐标 (i, j)的方案数。
• 可以从 dp[i - 1][j] 向下走到达 dp[i][j]
• 也可以从 dp[i][j - 1] 向右走到达 dp[i][j]

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

还有边界条件，当 i = 0 或 j = 0 时，都只有一种方案到达该位置（一直向右或一直向下）

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n));
    for (int row = 0; row < m; ++row) {
        dp[row][0] = 1;
    }
    for (int col = 0; col < n; ++col) {
        dp[0][col] = 1;
    }

    for (int row = 1; row < m; ++row) {
        for (int col = 1; col < n; ++col) {
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
        }
    }
    return dp[m - 1][n - 1];
}

dp[i][j] 的值只和 左侧 和 上方的值有关，空间上可以优化

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

    for (int row = 1; row < m; ++row) {
        for (int col = 1; col < n; ++col) {
            dp[col] += dp[col - 1];
        }
    }
    return dp[n - 1];
}