1. 面试题 17.16. 按摩师（LCR 089. 打家劫舍）
状态表示：dp[i] 表示选到 i 位置时的最长预约时长，当选到 i 位置时又有选和不选两种状态，又可以分为： f[i] 表示当前位置选的情况下的最长预约时长，g[i] 表示当前位置不选的情况下的最长预约时长
状态转移方程：
如果当前位置选的话，那么 i - 1 的位置肯定就不能选，也就是在 0 ~ i - 1 的范围内找到一个最大的预约时长，恰好 g[i - 1] 就表示 i - 1 位置不选的最大预约时长，再加上 nums[i] 即可
如果当前位置不选的话，那么 i - 1 的位置就可能会选，也可能不选，选的话就是 f[i - 1]，不选就是 g[i - 1]，选和不选两个状态取最大值即可
初始化：f[0] 就是 num[0]，g[0] 就是 0
填表顺序：从左往右两个表一起填
返回值：f[n - 1] 和 g[n - 1] 的最大值
class Solution { public int massage(int[] nums) { if(nums.length == 0) return 0; int n = nums.length; int[] g = new int[n]; int[] f = new int[n]; f[0] = nums[0]; for(int i = 1;i < nums.length;i++){ g[i] = Math.max(f[i - 1],g[i - 1]); f[i] = g[i - 1] + nums[i]; } return Math.max(g[n-1],f[n-1]); } }
2. 打家劫舍 II
和上一题不同的是，本题是一个环形的，也就是第一个偷了之后最后一个就不能偷了，两个只能偷一个，那么只需要把这个环形的转化为线性的即可，先计算偷第一个的情况，那么就是从 2 ~ n - 2 区间内就是正常线性的，如果第一个不偷的话就是 1 ~ n - 1 区间内是正常线性的情况，这两种情况取一个最大值即可，代码直接调用上一题就行
class Solution { public int rob(int[] nums) { int n = nums.length; return Math.max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1)); } public int rob1(int[] nums, int x, int y) { if (x > y) return 0; int m = nums.length; int[] g = new int[m]; int[] f = new int[m]; g[x] = 0; f[x] = nums[x]; for (int i = x + 1; i <= y; i++) { g[i] = Math.max(f[i - 1], g[i - 1]); f[i] = g[i - 1] + nums[i]; } return Math.max(g[y], f[y]); } }
3. 删除并获得点数
这一题其实还可以当做打家劫舍来做
arr[i] 表示 i 这个数字出现的总和，转化之后的 arr 数组就可以按照打家劫舍的规则来做了，题中要求的是 num[i] + 1 和 num[i] - 1 的数要删除，不能获取点数，也就是和打家劫舍中相邻的不能洗劫一个道理
class Solution { public int deleteAndEarn(int[] nums) { int[] arr = new int[10005]; for(int x : nums){ arr[x] += x; } int n = arr.length; int[] f = new int[n]; int[] g = new int[n]; f[0] = arr[0]; for(int i = 1;i < n;i++){ f[i] = g[i - 1] + arr[i]; g[i] = Math.max(f[i - 1],g[i - 1]); } return Math.max(f[n - 1],g[n - 1]); } }
4. LCR 091. 粉刷房子
状态表示：
dp[i][0] 表示粉刷到 i 号房子时粉刷上红色的最小花费
dp[i][1] 表示粉刷到 i 号房子时粉刷上蓝色的最小花费
dp[i][2] 表示粉刷到 i 号房子时粉刷上绿色的最小花费
状态转移方程：
当 i 位置粉刷红色的时候，上一个位置就需要是绿色或者蓝色了，也就是在上一个位置刷绿色和蓝色的最小花费之下再找出二者的最小值，加上 i 位置刷红色的花费
i 位置刷蓝色和绿色也是一样的道理
初始化：需要多加一行，为了不影响 0 号房子，加的那一行直接设为 0 即可
填表顺序：从上到下
返回值：红蓝绿三种情况的最小值
class Solution { public int minCost(int[][] costs) { int n = costs.length; int[][] dp = new int[n + 1][4]; for(int i = 1;i <= costs.length;i++){ dp[i][1] = Math.min(dp[i - 1][2],dp[i - 1][3]) + costs[i - 1][0]; dp[i][2] = Math.min(dp[i - 1][1],dp[i - 1][3]) + costs[i - 1][1]; dp[i][3] = Math.min(dp[i - 1][1],dp[i - 1][2]) + costs[i - 1][2]; } return Math.min(Math.min(dp[n][1],dp[n][2]),dp[n][3]); } }
