代码随想录算法训练营第三十九天 | 62.不同路径、 63. 不同路径 II

本文主要是介绍代码随想录算法训练营第三十九天 | 62.不同路径、 63. 不同路径 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：62.不同路径

文章讲解：代码随想录 62.不同路径讲解

视频讲解：动态规划中如何初始化很重要！| LeetCode：62.不同路径

思路和解法

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

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

问总共有多少条不同的路径？
想法：
今天主要的收获就是dp数组扩展到了二维的情况。同样复习了动态规划五部曲。感觉dp题目的逻辑比前面的还简单。

class Solution {
public://动规五部曲//1、确定dp数组及下标的含义 dp[i][j]:从下标[0][0]开始走到[i][j]的路径数//2、递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]//3、dp数组初始化 第一行和第一列都只有一种路径//4、确定遍历顺序：从第二行开始 一行一行遍历//5、举例推导dp数组int uniquePaths(int m, int n) {//数组用vector 每次都忘vector<vector<int>> dp(m, vector<int>(n, 0));for (int i = 0; i < m; i++) {dp[i][0] = 1;}for (int i = 0; i < n; i++) {dp[0][i] = 1;}//按行遍历 外层就是遍历mfor (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

文章讲解：代码随想录 63. 不同路径 II讲解

视频讲解：动态规划，这次遇到障碍了| LeetCode：63. 不同路径 II

思路和解法

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

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

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

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

class Solution {
public://和不同路径题目是完全一样的思路 只是要考虑障碍物//核心点就在于初始化的时候和递推的时候 初始化第一行或第一列遇到障碍物 后面的就都走不到了 都是0//递推时遇到障碍物也是0 因为走不到 在代码里就体现为跳过 因为初始化都是0//复习五部曲//1、确定dp数组及下标含义//2、递推公式//3、dp数组初始化//4、确定遍历顺序 目前就一维和二维两种//5、举例推导dp数组int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();//第一遍忘记了特殊情况 这道题目 障碍物有可能出现在起点和终点if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {return 0;}vector<vector<int>> dp(m, vector<int>(n, 0));for (int i = 0; i < m; i++) {if (obstacleGrid[i][0] == 1) {break;}dp[i][0] = 1;}for (int i = 0; i < n; i++) {if (obstacleGrid[0][i] == 1) {break;}dp[0][i] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};