【动态规划】多歧路 , 今安在? - 路径问题
【动态规划】多歧路 , 今安在? - 路径问题
1. 不同路径
题目链接: 62. 不同路径
题目内容:
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28
示例 2：
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
提示：
1 <= m, n <= 100 题目数据保证答案小于等于 2 * 109
第一 步骤分析
1.状态表示 dp[i][j]表示 以 [i,j] 位置为结尾所有不同路径的总数.
2. 状态转移方程
从[ i , j ] 最近的位置分析, 要想走到[ i , j ]位置,有两种情况: 第一种情况: 从[i-1 , j]位置向下一步, 总共有dp[i-1,j]种路径. 第二种情况: 从[i , j-1]位置向右一步, 总共有dp[i , j-1]种路径. 所以dp[i][j] = dp[i-1][j] + dp[i,j-1];
3. 初始化 使用上篇文章所说的初始化的技巧创建dp[m+1][n+1],此时dp中第一行和第一列是"虚拟"的, dp表的第2行和第2列都想初始化为一, 只需将dp[0][1] = 1, 按填表的递推公式,就可以做到.
4. 填表顺序 从上往下, 从左往右.
5. 返回值 返回dp[m][n];
第二 代码实现
class Solution {
public int uniquePaths(int m, int n) {
不添加虚拟节点的做法如下, 一般能添加还是尽量添加,因为后续有一些题目,不添加将很难处理初始化.
//1.创建dp表
//2.初始化
//3.填表
//4.返回值
// //1.创建dp表
// int[][] dp = new int[m][n];
// //2.初始化第一列
// for(int i = 0;i < m;i++) {
// dp[i][0] = 1;
// }
// //初始化第一行
// for(int i = 0;i < n;i++) {
// dp[0][i] = 1;
// }
// //3.填表
// 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];
//添加虚拟节点(第一行和第一列)的做法
int[][] dp = new int[m+1][n+1];
//画图分析初始化
dp[0][1] = 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][n];
}
}2. 不同路径 II
题目链接: 63. 不同路径 ||
题目内容:
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。
示例 1：
示例 2：
提示：
m == obstacleGrid.length n == obstacleGrid[i].length 1 <= m, n <= 100 obstacleGrid[i][j] 为 0 或 1
第一 步骤分析
1. 状态表示 dp[i][j] 表示以[i,j]位置为结尾的所有不同路径的总数.
2. 状态转移方程
想要得出dp[i][j]的递推公式,从[i,j]的相邻位置入手,根据题意机器人每次只能向下或者向右移动一步.所以从[i-1,j] 和 [i,j-1] 入手. 在[i,j]位置不是障碍物的情况下 [i-1,j] 到 [i,j] 路径数为: dp[i-1][j] [i,j-1] 到 [i,j] 路径数为: dp[i][j-1] dp[i][j] = dp[i-1][j] + dp[i][j-1]; [i,j]位置是障碍物: dp[i][j] = 0;
3. 初始化
如图所示, 创建的dp表比原数组多了一行一列,这一行一列的节点为虚拟节点. 创建好dp表后需要处理两个细节 第一个 dp表与原数组之间地下标对应关系是: dp[i][j] -> obstacleGrid[i-1][j-1] (此处理的作用在这一道题体现不明显,下一道题有所体现.) 第二个 虚拟节点的初始化: dp表中的第二行和第二列必然都是1值, 即只有一条不同的路径, 对应到原数组的第一行和第一列,从[0,0]位置开始沿着横线或者竖线直直地走就是只有一条路经. 虚拟节点地初始化就是为了将dp表的第一行和第一列初始化为1. 易得dp[0][1] = 1即可, dp[1][0] = 1也可.
4. 填表顺序 从上往下填写每一行 从左往右填写每一列
5. 返回值 看题意知, 返回dp[m][n]即可
第二 代码实现
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//1. 创建dp表
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m+1][n+1];
//2. 初始化
dp[0][1] = 1;
//3. 填表
for(int i = 1;i <= m;++i) {
for(int j = 1;j <= n;++j) {
if(obstacleGrid[i-1][j-1] != 1) dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m][n];
}
}3. 珠宝的最高价值
题目链接: LCR 166. 珠宝的最高价值
题目内容:
现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：
只能从架子的左上角开始拿珠宝 每次可以移动到右侧或下侧的相邻位置 到达珠宝架子的右下角时，停止拿取 注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。
示例 1:
输入: frame = [[1,3,1],[1,5,1],[4,2,1]] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝
提示：
0 < frame.length <= 200 0 < frame[0].length <= 200
第一 步骤分析
1. 状态表示 通常来讲都是以[i,j]为结尾 … 如果这么定义解不出来那么就定义成从[i,j]开始到达终点… 本题dp[i][j]表示 以 [i,j]位置为结尾, 所有珠宝价值和最高.
2. 状态转移方程
如果dp[i-1][j] > dp[i][j-1], 那么dp[i][j] += dp[i-1][j] + f[i][j]; 否则 dp[i][j] += dp[i][j-1] + f[i][j]; 综上, dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + f[i][j];
3. 初始化
处理两个细节 第一 dp表与原数组的对应关系: dp[i][j] -> f[i-1][j-1]; 第二 初始化虚拟节点, 由于虚拟节点默认值0不影响填表的正确性,所以不做处理.
4. 填表顺序 从上到下填写每一行 从左到右填写每一列
5. 返回值 返回dp[m][n]
第二 代码实现
class Solution {
public int jewelleryValue(int[][] f) {
int m = f.length;
int n = f[0].length;
int[][] dp = new int[m+1][n+1];
for(int i = 1;i <= m;++i) {
for(int j = 1;j <= n;++j) {
// if(dp[i-1][j] >= dp[i][j-1]) {
// dp[i][j] += dp[i-1][j] + f[i-1][j-1];
// }else {
// dp[i][j] += dp[i][j-1] + f[i-1][j-1];
// }
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+f[i-1][j-1];
}
}
return dp[m][n];
}
}本篇博客到这里就结束啦, 感谢观看 ❤❤❤
🐎期待与你的下一次相遇😊😊😊
腾讯云开发者
