题解 | #不同路径的数目(一)#

题目主要信息：

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

举一反三：

学习完本题的思路你可以解决如下题目：

BM68.矩阵的最小路径和

方法一：递归(推荐使用)

知识点：递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

思路：

首先我们在左上角第一个格子的时候，有两种行走方式：如果向右走，相当于后面在一个$(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$矩阵的子问题，因此可以使用递归。

具体做法：

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

图示：

Java实现代码：

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

C++实现代码：

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

Python代码实现：(Python版本超时，不能完全通过)

import sys
#设置递归深度
sys.setrecursionlimit(100000) 
class Solution:
    def uniquePaths(self , m: int, n: int) -> int:
        #矩阵只要有一条边为1，路径数就只有一种了
        if m == 1 or n == 1: 
            return 1
        else: 
            #两个分支
            return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

复杂度分析：

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

方法二：动态规划（扩展思路）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

思路：

如果我们此时就在右下角的格子，那么能够到达该格子的路径只能是它的上方和它的左方两个格子，因此从左上角到右下角的路径数应该是从左上角到它的左边格子和上边格子的路径数之和，因此可以动态规划。

具体做法：

• step 1：用dp[i][j]表示大小为$i\ast ji*j$的矩阵的路径数量，下标从1开始。
• step 2：（初始条件） 当i或者j为1的时候，代表矩阵只有一行或者一列，因此只有一种路径。
• step 3：（转移方程） 每个格子的路径数只会来自它左边的格子数和上边的格子数，因此状态转移为$dp[i][j]=dp[i-1][j]+dp[i][j-1]dp[i][j]\; =\; dp[i\; -\; 1][j]\; +\; dp[i][j\; -\; 1]$。

图示：

Java实现代码：

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

C++实现代码：

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

Python代码实现：

class Solution:
    def uniquePaths(self , m: int, n: int) -> int:
        #dp[i][j]表示大小为i*j的矩阵的路径数量
        dp = [[0] * (n + 1) for i in range(m + 1)] 
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                #只有1行的时候，只有一种路径
                if i == 1: 
                    dp[i][j] = 1
                    continue
                #只有1列的时候，只有一种路径
                if j == 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)!\}$种情况。

具体做法：

• step 1：分子分母从1开始；
• step 2：按照公式累乘相除。

Java实现代码：

import java.util.*;
public 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;
    }
}

C++实现代码：

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;
    }
};

Python代码实现：

class Solution:
    #计算阶乘
    def fun(self, n: int) -> int: 
        sum = 1
        #连乘
        for i in range(1, n + 1):
            sum *= i
        return sum
    def uniquePaths(self , m: int, n: int) -> int:
        #公式计算
        return self.fun(m + n - 2) // (self.fun(m - 1) * self.fun(n - 1))

复杂度分析：

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