【动态规划】代码随想录算法训练营第三十九天 |62.不同路径，63.不同路径II（待补充）

蔚落 2024-04-23 04:25 74阅读 0赞

## 62.不同路径 ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode]

2、文章讲解：[代码随想录][Link 1]

3、题目：

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

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

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

示例 1：

![32bc1a30ed907d1b5a5ec37684ef699a.png][]

*  输入：m = 3, n = 7
 *  输出：28

示例 2：

*  输入：m = 2, n = 3
 *  输出：3

解释： 从左上角开始，总共有 3 条路径可以到达右下角。

1.  向右 -> 向右 -> 向下
2.  向右 -> 向下 -> 向右
3.  向下 -> 向右 -> 向右

示例 3：

*  输入：m = 7, n = 3
 *  输出：28

示例 4：

*  输入：m = 3, n = 3
 *  输出：6

提示：

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

4、视频讲解：

[动态规划中如何初始化很重要！| LeetCode：62.不同路径\_哔哩哔哩\_bilibili][LeetCode_62._bilibili]

/**
     * 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
     */
    class Solution {
        public 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];
    
        }
    }

## 63.不同路径II ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

![874ea1801afe38077f19502d6d3ba1d7.png][]

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

![d1a83ab349c3c23d555cdc689b8d70c9.png][]

*  输入：obstacleGrid = \[\[0,0,0\],\[0,1,0\],\[0,0,0\]\]
 *  输出：2 解释：
 *  3x3 网格的正中间有一个障碍物。
 *  从左上角到右下角一共有 2 条不同的路径：

1.  1.  向右 -> 向右 -> 向下 -> 向下
    2.  向下 -> 向下 -> 向右 -> 向右

示例 2：

![04a500d3b3c83df2445d354832af5402.png][]

*  输入：obstacleGrid = \[\[0,1\],\[0,0\]\]
 *  输出：1

提示：

*  m == obstacleGrid.length
 *  n == obstacleGrid\[i\].length
 *  1 <= m, n <= 100
 *  obstacleGrid\[i\]\[j\] 为 0 或 1

4、视频链接：

[动态规划，这次遇到障碍了| LeetCode：63. 不同路径 II\_哔哩哔哩\_bilibili][LeetCode_63. _ II_bilibili]

class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[][] dp = new int[m][n];
    
            //如果在起点或终点出现了障碍，直接返回0
            if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
                return 0;
            }
    
            for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
                dp[i][0] = 1;
            }
            for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
                dp[0][j] = 1;
            }
    
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
                }
            }
            return dp[m - 1][n - 1];
        }
    }

[. - _LeetCode]: https://leetcode.cn/problems/unique-paths/
[Link 1]: https://www.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
[32bc1a30ed907d1b5a5ec37684ef699a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e2b72f0b03ee4afc81596ae231714e02.png
[LeetCode_62._bilibili]: https://www.bilibili.com/video/BV1ve4y1x7Eu/
[. - _LeetCode 1]: https://leetcode.cn/problems/unique-paths-ii/
[Link 2]: https://www.programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[874ea1801afe38077f19502d6d3ba1d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/16895ce2626445d2a69274c80f8399d6.png
[d1a83ab349c3c23d555cdc689b8d70c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/68d9b77d35a54d3a8c188fb165c7cf15.png
[04a500d3b3c83df2445d354832af5402.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/f9ad7fc05aa543279489b8d5720ef2e3.png
[LeetCode_63. _ II_bilibili]: https://www.bilibili.com/video/BV1Ld4y1k7c6/