题目描述

一个机器人站在m x n的网格的左上角，它只能向下或向右走，如果它想走到网格的右下角，可能有多少种唯一的路径呢？

样例

输入: m = 2, n = 2
输出: 2
解释：网格大小为2x2，观察易知机器人共两条路线。

算法1

(递归) $O(2^{m+n})$

每一个网格都可以由该网格左边或上边的网格转移过来，因此到达某一点的路径数等于到达它上一点的路径数与它左边的路径数之和，其实这是一个递推问题，即(m, n)的路径数等于(m, n-1)和(m-1, n)的路径之和，再考虑边界情况，就是当网格长/宽==1时，只有一条路径。
递推公式即
$$ \left\{ \begin{aligned} T(m, n) & = &1\text{ , if m == 1 or n == 1}\\ T(m, n) & = &T(m-1, n) + T(m, n-1)\text{ , else} \end{aligned} \right. $$
但由于直接递归会产生大量重复计算导致复杂度很高，当m, n较大时容易超时，因此需要数组记录一下中间值，这样再次需要用到时查表即可，用数组记录后复杂度变为$O(mn)$。

C++ 代码

直接递归：

class Solution {
public:
    int uniquePaths(int m, int n) {  
        if (m == 1 || n == 1) return 1;  
        return uniquePaths(m, n - 1) + uniquePaths(m - 1, n);  
    }  
};

数组记录中间值：

class Solution {
public:
    int record[101][101];
    int help(int m, int n){
        if(m == 1 || n == 1)
            return 1;
        if(record[m][n] > 0)//说明有记录
            return record[m][n];
        record[m][n] = help(m - 1, n) + help(m, n - 1);
        return record[m][n];
    }
    int uniquePaths(int m, int n) {  
        memset(record, 0, sizeof(record));
        return help(m, n);
    }  
};

算法2

(动态规划) $O(mn)$

如上所述，这是一个递推问题, 因此可以考虑动态规划。动态规划数组dp[i][j] = 起点到点(i, j)的路径总数。于是我们就得到递推关系式：dp[i][j] = dp[i][j-1] + dp[i-1][j]。再考虑边界情况，当i == 1 || j == 1时，dp[i][j] = 1。

C++ 代码：

class Solution {
public:
    int uniquePaths(int m, int n) {  
        int dp[101][101];
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(i == 1 || j == 1)
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }  
};

上述做法需要一个大小为m x n的二维数组，空间复杂度为$O(mn)$，但其实dp[i][j]只会用到dp[i-1][j]和dp[i][j-1]，不会用到之前的数据，因此可以用滚动数组减小空间复杂度。

C++ 代码：

class Solution {
public:
    int uniquePaths(int m, int n) {  
        int dp[101];
        memset(dp, 0, sizeof(dp));
        dp[1] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = 2; j <= n; j++){
                dp[j] += dp[j-1];
            }
        }
        return dp[n];
    }  
};

算法3

(组合数学) $O(n)$

从网格左上角到网格右下角一共要走m+n-2步，在这些步数中，一共会向下走m-1步，向右走n-1步，因此就是经典的组合问题，结果就是$C_{m+n-2}^{n-1}$。这样空间复杂度为$O(1)$，时间复杂度为$O(n)$。

C++ 代码：

class Solution {
public:
    int uniquePaths(int m, int n) {  
        int totalStep = m + n - 2;
        int step = max(m , n);
        long long res = 1;
        for(int i = step; i <= totalStep; i++)
            res *= i;
        for(int i = 1; i <= totalStep - step + 1; i++)
            res /= i;
        return (int)res;
    }  
};