动态规划 之 路径问题 算法专题
一. 差别路径差别路径
[*]状态表示
dp 表示走到位置, 有几种差别的路径
[*]状态转移方程
以离 近来的位置划分问题
1.从 到, 到位置的差别路径数 就是和 到位置的差别路径数雷同, 即dp = dp
2.从 到, 到位置的差别路径数 就是和 到位置的差别路径数雷同, 即dp = dp
[*]dp = dp + dp
[*] 初始化
使用优化的思想进行初始化, 添加虚拟节点
在第一行和第一列的位置填表时会发生越界
所以须要添加一行一列
https://i-blog.csdnimg.cn/direct/4e4250873e484d958d1d8e52cc63402c.png
我们只须要像上表一样初始化虚拟节点, 就可以正确的进行填表
[*] 填表顺序
从上往下 从左往右
[*] 返回值
返回dp
class Solution {
public int uniquePaths(int m, int n) {
//1. 创建表
//2. 初始化
//3. 填表
//4. 返回值
int[][] dp = new int;
dp = 1;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
dp = dp + dp;
}
}
return dp;
}
}
二. 差别路径II
差别路径II
[*]状态表示
dp 表示走到位置, 有几种差别的路径
[*]状态转移方程
以离 近来的位置划分问题
1.从 到, 到位置的差别路径数 就是和 到位置的差别路径数雷同, 即dp = dp
2.从 到, 到位置的差别路径数 就是和 到位置的差别路径数雷同, 即dp = dp
但是如果此时的是停滞物, 那么到达这个位置的路径数就为0, 所以dp = 0
[*]dp = dp + dp
[*] 初始化
使用优化的思想进行初始化, 添加虚拟节点
在第一行和第一列的位置填表时会发生越界
所以须要添加一行一列
https://i-blog.csdnimg.cn/direct/4e4250873e484d958d1d8e52cc63402c.png
我们只须要像上表一样初始化虚拟节点, 就可以正确的进行填表
[*] 填表顺序
从上往下 从左往右
[*] 返回值
返回dp
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//1. 创建表
//2. 初始化
//3. 填表
//4. 返回值
int m = obstacleGrid.length;
int n = obstacleGrid.length;
int[][] dp = new int;
dp = 1;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(obstacleGrid == 1) {
dp = 0;
}else{
dp = dp + dp;
}
}
}
return dp;
}
}
三. 珠宝的最高代价
珠宝的最高代价
[*]状态表示
dp 表示走到位置, 得到的珠宝的最高代价是多少
[*]状态转移方程
以离 近来的位置划分问题
到位置的得到的珠宝的最高代价 就是到位置的得到的珠宝的最高代价 与 到位置的得到的珠宝的最高代价 的最大值, 然后加上位置原来的代价
[*]dp = max(dp + dp) + frame(采用优化的思想, 与原下标对应要 - 1)
[*]初始化
使用优化的思想进行初始化, 添加虚拟节点
在第一行和第一列的位置填表时会发生越界
所以须要添加一行一列
我们只须要将虚拟节点都设为0即可
[*]填表顺序
从上往下 从左往右
[*]返回值
返回dp
class Solution {
public int jewelleryValue(int[][] frame) {
//1. 创建dp
//2. 初始化
//3. 填表
//4. 返回值
int m = frame.length;
int n = frame.length;
int[][] dp = new int;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
dp = Math.max(dp, dp) + frame;
}
}
return dp;
}
}
四. 降落路径最小和
降落路径最小和
[*]状态表示
dp 表示走到位置, 路径的最小和
[*]状态转移方程
以离 近来的位置划分问题
到位置的路径的最小和 就是到位置路径的最小和 与 到位置路径的最小和 与 位置路径的最小和 的最小值, 然后加上位置原来的值
[*]dp = Math.min(Math.min(dp, dp), dp) + matrix(采用优化的思想, 与原下标对应要 - 1)
[*]初始化
使用优化的思想进行初始化, 添加虚拟节点
在第一行和第一列和末了一列的位置填表时会发生越界
所以须要添加一行两列
我们须要将虚拟节点都设为最大值, 防止对原来的数进行干扰
[*]填表顺序
从上往下 从左往右
[*]返回值
返回末了一行中的最小值
class Solution {
public int minFallingPathSum(int[][] matrix) {
//1. 创建dp
//2. 初始化
//3. 填表
//4. 返回值
int n = matrix.length;
int[][] dp = new int;
for(int i = 1; i <= n; i++){
dp = Integer.MAX_VALUE;
dp = Integer.MAX_VALUE;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dp = Math.min(Math.min(dp, dp), dp) + matrix;
}
}
int min = Integer.MAX_VALUE;
for(int j = 1; j <= n; j++){
min = Math.min(min, dp);
}
return min;
}
}
五. 最小路径和
最小路径和
[*]状态表示
dp 表示走到位置, 路径的最小和
[*]状态转移方程
以离 近来的位置划分问题
到位置的路径的最小和 就是到位置路径的最小和 与 位置路径的最小和 的最小值, 然后加上位置原来的值
[*]dp = Math.min(dp, dp) + grid(采用优化的思想, 与原下标对应要 - 1)
[*]初始化
使用优化的思想进行初始化, 添加虚拟节点
在第一行和第一列的位置填表时会发生越界
所以须要添加一行一列
我们须要将虚拟节点设为最大值, 但是位置的值要设为0, 防止对原来的数进行干扰
[*]填表顺序
从上往下 从左往右
[*]返回值
dp
class Solution {
public int minPathSum(int[][] grid) {
// 1. 创建dp
// 2. 初始化
// 3. 填表
// 4. 返回值
int m = grid.length;
int n = grid.length;
int[][] dp = new int;
for (int i = 0; i <= m; i++) {
dp = Integer.MAX_VALUE;
}
for (int j = 0; j <= n; j++) {
dp = Integer.MAX_VALUE;
}
dp = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp = Math.min(dp, dp) + grid;
}
}
return dp;
}
}
六. 地下城游戏
地下城游戏
[*]状态表示
dp 如果表示走到位置, 所须要的最小血量, 是没办法完成这道题的, 由于, 每走一步, 所需的最小血量都在更新
所以dp 表示从位置开始, 所须要的最小血量
[*]状态转移方程
以离 近来的位置划分问题
1.位置所须要的最小血量 + 位置须要加或减的血量 一定是要 >= 到位置所须要的最小血量, 才能保证走下一个位置的时候不会死, 所以dp = dp - 原表的
2.位置所须要的最小血量 + 位置须要加或减的血量 一定是要 >= 到位置所须要的最小血量, 才能保证走下一个位置的时候不会死, 所以dp = dp - 原表的
[*]dp = Math.min(dp, dp) - 原表的
但是我们得出的dp 必须是>0的, 如果<0, 就设为1, 所须要的最低血量
[*]初始化
使用优化的思想进行初始化, 添加虚拟节点
在末了一行和末了一列的位置填表时会发生越界
所以须要添加一行一列
我们须要将虚拟节点设为最大值, 但是位置 和位置 的值要设为1, 所须要的最低血量
[*]填表顺序
从下往上 从右往左
[*]返回值
dp
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
// 1. 创建dp
// 2. 初始化
// 3. 填表
// 4. 返回值
int m = dungeon.length;
int n = dungeon.length;
int [][] dp = new int;
for(int i = m; i >= 0; i--){
dp = Integer.MAX_VALUE;
}
for(int j = n; j >= 0; j--){
dp = Integer.MAX_VALUE;
}
dp = dp = 1;
for(int i = m - 1; i >= 0; i--){
for(int j = n - 1; j >=0; j--){
dp = Math.min(dp, dp) - dungeon;
dp = Math.max(1, dp);
}
}
return dp;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]