题目链接: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;
}
//按行遍历 外层就是遍历m
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
文章讲解:代码随想录 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];
}
};