一、最小路径和
先看一眼题干什么意思-我们可以知道，左上角到右下角的最小路径和
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
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.返回值
两者中最大值
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]); } }
