蓝桥杯必备动态规划第二弹-路径问题进阶-Toy模板网

这篇具有很好参考价值的文章主要介绍了蓝桥杯必备动态规划第二弹-路径问题进阶。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、最小路径和

最小路径和

先看一眼题干什么意思-我们可以知道，左上角到右下角的最小路径和

1.状态表示（第一步其实是最重要，因为他可以确定状态转移方程）

dp[i][j]:到ij位置，路径之和是最小

2.状态转移方程（为什么这么写，首先你要能到ij位置，其次你需要+ij位置的数字）

dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1]

3.初始化

左边可以多一行，上面可以多一行，也就是虚拟节点

因为他是要求最小值，但是左侧，和上面都会有一处影响填表，所以这两个的值不能是0.

4.初始化

从上到下，从左到右

5.返回值

return dp[i][j]

这个代码正确解法
class Solution {
    public int minPathSum(int[][] grid) {
    int m=grid.length,n=grid[0].length;
    int [][]dp=new int[m+1][n+1]; 
     
    for(int i=2;i<m+1;i++){
        for(int j=2;j<n+1;j++){
        dp[i][0]=Integer.MAX_VALUE;
         dp[0][j]=Integer.MAX_VALUE;
        }
    }
    for(int j=2;j<n+1;j++){
        dp[0][j]=Integer.MAX_VALUE;
    }
    for(int i=1;i<m+1;i++){
        for(int j=1;j<n+1;j++){
        dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
        }
    }
return dp[m][n];
    }
}

二、地下城游戏

地下城勇士

1.状态表示

dp[i][j]:假如说表示结尾是否可以表示呢？

也就是到达ij位置时候dp[i][j]需要最小的血量

但是到达i j位置他是由上一个[i-1][j]位置决定，然后在加上那个格子[i][j],然后最后剩1滴血起码。

2.状态转移方程

dp[i][j]=min(dp[i-1][j],dp[i][j-1])+dungeon[i][j]

3.初始化

如果能活着最少一滴血，其余是正无穷

4.顺序

从上到下，从左到右

5.返回值

dp[0][0]
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
 int m=dungeon.length,n=dungeon[0].length;
    int [][]dp=new int[m+1][n+1]; 
    
    for(int i=0;i<m+1;i++){
        for(int j=0;j<n+1;j++){
        dp[i][n]=Integer.MAX_VALUE;
         dp[m][j]=Integer.MAX_VALUE;
        }
    }
    dp[m-1][n]=dp[m][n-1]=1;
    for(int i=m-1;i>=0;i--){
        for(int j=n-1;j>=0;j--){     
        dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]; 
         dp[i][j]=Math.max(1,dp[i][j]);
          
        }
    }
   
return dp[0][0];
    }
}

三、按摩师

蓝桥杯必备动态规划第二弹-路径问题进阶,动态规划,算法

1.状态表示

dp[i]:以i位置结尾的，最大预约时间,但是他应该能更加细节化

f[i]:以i位置结尾的处于休息时间，最大预约时间

g[i]:以i位置结尾的处于完事时间，最大预约时间

2.状态转移方程

f[i]有两种状态第一种就是我最后一个没有选择，但是我前一个一定选了[i-1]，所以f[i]=g[i-1],他还有另一种选择，就是也不选i-1的位置，那样的话，大家是不是也很困惑，那样不就不是最大了吗，这样不也没意义吗，其实不然，假如说是【2，1，1，2】这样的，你怎么处理呢】，是不是i-1节点前面的不能选，i-2节点也不能选，最后一个选，是用的g[i]，但是g[]g[i]=f[i-1]+d[i]

3.初始状态

可以虚拟节点，可以不用虚拟节点，不用节点的话，g[0]=nums[0]保证这个即可

假如说使用虚拟节点，就是左侧添加一个格子，但是这个格子也是0，所以用不用都行，那么g[1]=nums[0],注意下标的对应。

4.顺序

从左到右

5.返回值

return Math.max(f[m-1],g[m-1].

class Solution {
    public int massage(int[] nums) {
     int m=nums.length;
     if(m==0){
         return 0;
     }
     int []f=new int[m];
     int []g=new int[m];
     g[0]=nums[0];
     for(int i=1;i<m;i++){
         f[i]=Math.max(g[i-1],f[i-1]);
         g[i]=f[i-1]+nums[i];
     }
  
  return Math.max(f[m-1],g[m-1]);
    }
}

四、打家劫舍II

打家劫舍II

蓝桥杯必备动态规划第二弹-路径问题进阶,动态规划,算法

1.状态表示

dp[i]:以i位置结尾的今晚能偷到的最高金额

f[i]:以i位置结尾，偷这个房子，能偷到的最高金额

g[i]:以i位置结尾，不偷这个房子，能偷到的最高金额

2.状态表示

f[i]=g[i-1]+nums[i]

g[i]=max(f[i-1],g[i-1])

3.初始化

这里有一个卡了我一天的一个细节，就是Maxsum里面初始化，一直我是想的是f[0]=n[0],这个样子。f[a]就其实等于f[0],因为是从a位置开始填写，其次它是从a+1开始，第0天就对应的我们生活中的第一天，因为要对应nums的下标。

4.填表顺序

从左到右，两个表一起填写

5.返回值

两者中最大值文章来源地址https://www.toymoban.com/news/detail-712917.html
class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        if(n==1){
            return nums[0];
        }
    int f= Maxsum(nums,0,n-2);
    int d= Maxsum(nums,1,n-1);   
    return Math.max(f,d);
    }
  public int Maxsum(int []n,int a,int b){
      if(a>b){
          return 0;
      }
    int m=n.length;
    int f[]=new int[m];
    int g[]=new int[m];
    f[a]=n[a];
    
    for(int i=a+1;i<=b;i++){ 
        f[i]=g[i-1]+n[i];
        g[i]=Math.max(f[i-1],g[i-1]);
    }
    return Math.max(g[b],f[b]);
}
}