【动态规划】简单多状态dp问题：按摩师，打家劫舍，删除并获得点数，粉刷房子，买卖股票的最佳时机

文章目录1. 按摩师 (面试题17.16)题目描述解题思路代码实现2. 打家劫舍II(LC 213)题目描述解题思路代码实现3. 删除并获得点数(LC 740)题目描述解题思路代码实现4. 粉刷房子(LCR091)题目描述解题思路代码实现1. 按摩师 (面试题17.16)按摩师题目描述解题思路状态表示到第i个元素累计最长时间为dp[i]。对于每个元素都可以选择接受或不接受。需要两个数组来表示f[i]表示接受当前预约的最长时间g[i]表示不接受当前预约的最长时间状态转移方程如果接受i预约前一个一定不接受。f[i] g[i-1] nums[i]如果不接受前一个预约可能接受也可能不接受。取最大值。g[i] max(f[i-1],g[i-1])初始化如果第一预约接受f[0] nums[0]不接受则g[i] 0代码实现classSolution{publicintmassage(int[]nums){intnnums.length;if(n0)return0;int[]fnewint[n];int[]gnewint[n];f[0]nums[0];for(inti1;in;i){f[i]g[i-1]nums[i];g[i]Math.max(f[i-1],g[i-1]);}returnMath.max(f[n-1],g[n-1]);}}2. 打家劫舍II(LC 213)打家劫舍II题目描述解题思路分类讨论把环形问题转换为线性问题。如果偷0号位置则1号和n-号不可以偷2号到n-2号可以偷变成了上一题的解法如果不偷0号位置则1号到n-号可以偷。代码实现classSolution{int[]nums;publicintrob(int[]_nums){nums_nums;intnnums.length;intcase1rob1(2,n-2,n)nums[0];intcase2rob1(1,n-1,n);returnMath.max(case1,case2);}introb1(intl,intr,intn){if(lr)return0;int[]fnewint[n];int[]gnewint[n];f[l]nums[l];for(intil;ir;i){f[i]g[i-1]nums[i];g[i]Math.max(f[i-1],g[i-1]);}returnMath.max(f[r],g[r]);}}3. 删除并获得点数(LC 740)删除并获得点数题目描述解题思路用数组hash记录每个数字出现的次数。这样就转换为第一个题用两个数组表示当前数字删或不删得到的总和。代码实现classSolution{publicintdeleteAndEarn(int[]nums){int[]hashnewint[10001];intmax0;for(intnum:nums){hash[num];maxMath.max(max,num);}int[]fnewint[max1];int[]gnewint[max1];g[1]hash[1];for(inti2;imax;i){f[i]Math.max(g[i-1],f[i-1]);g[i]f[i-1]hash[i]*i;}returnMath.max(f[max],g[max]);}}4. 粉刷房子(LCR091)粉刷房子题目描述解题思路与第一题类似只需要用三个数组做动态规划即可代码实现classSolution{publicintminCost(int[][]costs){intncosts.length;int[]rednewint[n];int[]bluenewint[n];int[]greennewint[n];red[0]costs[0][0];blue[0]costs[0][1];green[0]costs[0][2];for(inti1;in;i){red[i]Math.min(green[i-1],blue[i-1])costs[i][0];blue[i]Math.min(green[i-1],red[i-1])costs[i][1];green[i]Math.min(red[i-1],blue[i-1])costs[i][2];}returnMath.min(green[n-1],Math.min(red[n-1],blue[n-1]));}}