62.不同路径

小灰灰 2023-10-16 16:01 15阅读 0赞

#### 62.不同路径 ####

*  题干描述
 *  解题思路
 *   *  1. 深搜
     *  2. 动态规划
     *   *  2.1 确定dp数组（dp table）以及下标的含义
         *  2.2 确定递推公式
         *  2.3 dp数组的初始化
         *  2.4 确定遍历顺序
         *  2.5 举例推导dp数组
     *  3. 数论方法
 *  代码实现

## 题干描述 ##

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

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

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

示例：  
![在这里插入图片描述][a21e6fb00698485abbac22abd1b7bbe8.png]  
输入：m = 3, n = 7  
输出：28

提示：

*  1 <= m, n <= 100
 *  题目数据保证答案小于等于 2 \* 10^9

## 解题思路 ##

### 1. 深搜 ###

这道题目，刚一看最直观的想法就是用图论里的深搜，来枚举出来有多少种路径。

注意题目中说机器人每次只能向下或者向右移动一步，那么其实**机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点**！

如图举例：  
![在这里插入图片描述][c5518fd5bdd14866a14c5f55dd10d1f4.png]  
此时问题就可以转化为求二叉树叶子节点的个数。**大家如果提交了代码就会发现超时了！**

来分析一下时间复杂度，这个深搜的算法，其实就是要遍历整个二叉树。

这棵树的深度其实就是m+n-1（深度按从1开始计算）。

那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树（其实没有遍历整个满二叉树，只是近似而已）

所以上面深搜代码的时间复杂度为O(2^(m + n - 1) - 1)，可以看出，这是指数级别的时间复杂度，是非常大的。

### 2. 动态规划 ###

机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点。

按照动规五部曲来分析：

#### 2.1 确定dp数组（dp table）以及下标的含义 ####

dp\[i\]\[j\] ：表示从（0 ，0）出发，到(i, j) 有dp\[i\]\[j\]条不同的路径。

#### 2.2 确定递推公式 ####

想要求dp\[i\]\[j\]，只能有两个方向来推导出来，即dp\[i - 1\]\[j\] 和 dp\[i\]\[j - 1\]。

此时再回顾一下 dp\[i - 1\]\[j\] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp\[i\]\[j - 1\]同理。

那么很自然，dp\[i\]\[j\] = dp\[i - 1\]\[j\] + dp\[i\]\[j - 1\]，因为dp\[i\]\[j\]只有这两个方向过来。

#### 2.3 dp数组的初始化 ####

如何初始化呢，首先dp\[i\]\[0\]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp\[0\]\[j\]也同理。

所以初始化代码为：

for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;

#### 2.4 确定遍历顺序 ####

这里要看一下递推公式dp\[i\]\[j\] = dp\[i - 1\]\[j\] + dp\[i\]\[j - 1\]，dp\[i\]\[j\]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。

这样就可以保证推导dp\[i\]\[j\]的时候，dp\[i - 1\]\[j\] 和 dp\[i\]\[j - 1\]一定是有数值的。

#### 2.5 举例推导dp数组 ####

![在这里插入图片描述][44f0e02fcf854f7593c3273d0e622728.png]

### 3. 数论方法 ###

在这个图中，可以看出一共m，n的话，无论怎么走，走到终点都需要 m + n - 2 步。  
![在这里插入图片描述][789437f0c2ef4e29a7971b888ff1660a.png]  
在这m + n - 2 步中，一定有 m - 1 步是要向下走的，不用管什么时候向下走。

那么有几种走法呢？ 可以转化为，给你m + n - 2个不同的数，随便取m - 1个数，有几种取法。

那么这就是一个组合问题了。

那么答案，如图所示：  
![在这里插入图片描述][95bebce36f5b437da4ae77f51639a5f8.png]  
求组合的时候，要防止两个int相乘溢出！ 所以不能把算式的分子都算出来，分母都算出来再做除法。

## 代码实现 ##

class Solution {
        
       // 62. 不同路径
        /**
         * 1. 确定dp数组下标含义 dp[i][j]到每一个坐标可能的路径种类
         * 2. 递推公式 dp[i][j] = dp[i-1][j] dp[i][j-1]
         * 3. 初始化 dp[i][0] = 1 dp[0][i] = 1 初始化横竖就可
         * 4. 遍历顺序 一行一行遍历
         * 5. 推导结果 。。。。。。
         *
         * @param m
         * @param n
         * @return
         */
        public static int uniquePaths(int m, int n){
        
            int[][] dp = new int[m][n];
            // 初始化
            for(int i = 0; i < m; i++){
        
                dp[i][0] = 1;
            }
            for(int i = 0; i < n; i++){
        
                dp[0][i] = 1;
            }
            for(int i = 1; i < m; i++){
        
                for(int j = 1; j < n; j++){
        
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
            return dp[m-1][n-1];
        }
    }

**参考资料**：[代码随想录-62.不同路径][-62.]

[Link 1]: https://leetcode.cn/problems/unique-paths/
[a21e6fb00698485abbac22abd1b7bbe8.png]: https://img-blog.csdnimg.cn/a21e6fb00698485abbac22abd1b7bbe8.png
[c5518fd5bdd14866a14c5f55dd10d1f4.png]: https://img-blog.csdnimg.cn/c5518fd5bdd14866a14c5f55dd10d1f4.png
[44f0e02fcf854f7593c3273d0e622728.png]: https://img-blog.csdnimg.cn/44f0e02fcf854f7593c3273d0e622728.png
[789437f0c2ef4e29a7971b888ff1660a.png]: https://img-blog.csdnimg.cn/789437f0c2ef4e29a7971b888ff1660a.png
[95bebce36f5b437da4ae77f51639a5f8.png]: https://img-blog.csdnimg.cn/95bebce36f5b437da4ae77f51639a5f8.png
[-62.]: https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE