题解 | #求路径#

题目的主要信息：

• 给定一个m*n的矩阵，要求从矩阵的左上角走到右下角的不同路径数量
• 每次只能往下或者往右走

这道题非常典型，我们可以考虑多种方式。

方法一：递归

具体做法：

首先我们在左上角第一个格子的时候，有两种行走方式：如果向右走，相当于后面在一个$(n-1)\ast m(n-1)*m$的矩阵中查找从左上角到右下角的不同路径数；而如果向下走，相当于后面在一个$n\ast (m-1)n*(m-1)$的矩阵中查找从左上角到右下角不同的路径数。而$(n-1)\ast m(n-1)*m$的矩阵与$n\ast (m-1)n*(m-1)$的矩阵都是$n\ast mn*m$矩阵的子问题，因此可以使用递归。

• 终止条件： 当矩阵变长n减少到1的时候，很明显只能往下走，没有别的选择了，只有1条路径；同理m减少到1时也是如此。因此此时返回数量为1.
• 返回值： 对于每一级都将其两个子问题返回的结果相加返回给上一级。
• 本级任务： 每一级都有向下或者向右两种路径选择，分别进入相应分支的子问题。

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m == 1 || n == 1) //矩阵只要有一条边为1，路径数就只有一种了
            return 1;
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1); //两个分支
    }
};

复杂度分析：

• 时间复杂度：$O(mn)O(mn)$，其中$mm$、$nn$分别为矩阵的两边长，递归过程对于每个$mm$最多都要经过每一种$nn$
• 空间复杂度：$O(mn)O(mn)$，递归栈的最大深度

方法二：动态规划

具体做法：

如果我们此时就在右下角的格子，那么能够到达该格子的路径只能是它的上方和它的左方两个格子，因此从左上角到右下角的路径数应该是从左上角到它的左边格子和上边格子的路径数之和，因此可以动态规划，dp[i][j]表示大小为$i\ast ji*j$的矩阵的路径数量，下标从1开始。

• 初始条件： 当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]$。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0)); //dp[i][j]表示大小为i*j的矩阵的路径数量
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(i == 1){ //只有1行的时候，只有一种路径
                    dp[i][j] = 1;
                    continue;
                }
                if(j == 1){ //只有1列的时候，只有一种路径
                    dp[i][j] = 1;
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; //路径数等于左方格子的路径数加上上方格子的路径数
            }
        }
        return dp[m][n];
    }
};

复杂度分析：

• 时间复杂度：$O(mn)O(mn)$，其中$mm$、$nn$分别为矩阵的两边长，两层遍历填充整个dp数组
• 空间复杂度：$O(mn)O(mn)$，辅助空间dp数组

方法三：组合数学

具体做法：

从矩阵左上角走到矩阵右下角，总共需要往下走$m-1m-1$步，往右走$n-1n-1$步，不同的走法路径在于往下和往右的组合情况，即在一堆往下和往右的序列中，每种排列的情况，序列一共有$m+n-2m+n-2$个位置，选择其中$n-1n-1$个位置作为往下，即不同的走法有$C_{m+n-2}^{n-1}=\frac{(m+n-2)!}{(n-1)!(m-1)!}C^\{n-1\}\_\{m+n-2\}=\backslash frac\{(m+n-2)!\}\{(n-1)!(m-1)!\}$种情况。直接计算即可得到。

class Solution {
public:
    int uniquePaths(int m, int n) {
        long res = 1; //防止溢出
        for(int i = 1; i < n; i++)
            res = res * (m + i - 1) / i; //根据公式计算
        return (int)res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，计算过程需要从1遍历到n
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间