题目链接：https://leetcode-cn.com/problems/unique-paths/

难度：中等

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

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

测试用例

示例 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 * 109

题解

【方法一】：动态规划

时间复杂度：

空间复杂度：

机器人只能向右/向下走，所以若想到达第i行，第j列的位置，只有两种走法：

• 从第i-1行 第j列向下走一步；
• 从第i行，第j-1列向右走一步。

如下图：

那么我们设一个数组map[m, n]，其中map[i][j]表示到达第i行第j列位置的路径数量。则有递推公式：。特殊情况，当只有一行或一列时，只有一种路径（即走直线）。

到这里，大家肯定也想到了用递归（代码如下），但是，用递归会有很多重复计算，本人提交试了一下，直接超时。

超时的递归代码：

class Solution {
    public int uniquePaths(int m, int n) {
        return cal(m, n, 0, 0);
    }

    private int cal(int m, int n, int row, int col){
        if (row + 1 == m || col + 1 == n)
            return 1;
        return cal(m, n, row+1, col) + cal(m, n, row, col+1);
    }
}

正确的Java代码：

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] map = new int[m+1][n+1];

        for (int i = 1; i <= n; i++) // 第一行初始化为1
            map[1][i]  = 1;
        for (int i = 1; i <= m; i++) // 第一列初始化为1
            map[i][1] = 1;

        for (int i = 2; i <= m; i++)
            for (int j = 2; j <= n; j++)
                map[i][j] = map[i-1][j] + map[i][j-1]; // DP
        
        return map[m][n];
    }
}

【方法二】：组合数

时间复杂度：

空间复杂度：

因为机器人只能向右或向下走，所以到达第（m,n）处，需要向右走n-1步，向下走m-1步，一共走m+n-2步。因此路径的总数，就是从m+n-2步中选择m-1次向下走的方案数，即组合数：

计算的时候，我们可以使用m和n中最小的一个，更加节省时间。

代码如下：

class Solution {
    public int uniquePaths(int m, int n) {
        long ans = 1; // 注意这个地方，用int会溢出
        if (m > n){ // 取m为较小的一个
            int tmp = m;
            m = n;
            n = tmp;
        }
            
        for (int i = n, j = 1; j < m; i++, j++) // 计算组合数
            ans = ans * i / j;
        
        return (int)ans;
    }
}