【动态规划】打家劫舍类问题

一、按摩师

17.16. 按摩师

题目描述：

题目分析：

1、状态表示

每个预约都只会有两种选择，即选或不选。因此我们可以用

dp[i][0] 表示不选择第 i 个预约时，最长的预约时长
dp[i][1] 表示选择第 i 个预约时，最长的预约时长

2、状态转移方程

对于 dp[i][0] ：

如果我们选择了第 i 个预约，那么第 i-1 次预约就一定不会选择，这时我们只需要知道不选第 i-1 次预约时的最长预约时长即可，即 dp[i-1][0] 的值，再加上 num[i] 即可。可得递推公式就为：

dp[i][1]=dp[i-1][0]+nums[i]

对于 dp[i][1] ：

如果我们不选择第 i 个预约，那么第 i-1 次预约就可以被选择，当然也可以不选，这时我们只需要知道选或不选第 i-1 次预约时分别的最长预约时长即可，即 dp[i-1][0] 与 dp[i-1][0] 的值，取这两个中的最大值即可。可得递推公式就为：

dp[i][0]=Math.max(dp[i-1][1],dp[i-1][0])

3、初始化

为了避免 i-1 时越界，我们初始化dp表的长度为 n+1，然后从 i=1 开始遍历

要注意下标的映射关系，此时 nums[i-1] 表示nums中第 i 个元素

4、返回值

直接返回 Math.max(dp[n][0],dp[n][1])，因为我们不确定最后一个选不选。

代码实现：

java">class Solution {public int massage(int[] nums) {int n=nums.length;int[][] dp=new int[n+1][2];for(int i=1;i<=n;i++){dp[i][0]=Math.max(dp[i-1][1],dp[i-1][0]);dp[i][1]=dp[i-1][0]+nums[i-1];}return Math.max(dp[n][0],dp[n][1]);}
}

二、打家劫舍 II

213. 打家劫舍 II

题目描述：

题目分析：

其实这就是在上题的基础上做了一些限制。我们可以根据第一号房子是否选择来将问题抽象成两个模型：

偷第一号房子：此能就不能去偷第二号房子与第n号房子，就是还能偷 [3，n-1] 区间内的房子
不偷第一号房子：此时可以偷最后一个房子，也就是说可以偷 [2，n] 区间内的房子

我们可以将上题中的 “打家劫舍” 模型抽象出来，将求取 [1，n] 范围内的最优选改为设定的 [l，r] 范围内的最优选。只需要修改一下遍历时的边界即可

此时就将该问题抽象成了两个 “打家劫舍” 问题的最优解了。

代码实现：

java">class Solution {public int rob(int[] nums) {int n=nums.length;return Math.max(nums[0]+fun(nums,3,n-1),fun(nums,2,n));}public static int fun(int[] nums,int l,int r){int[][] dp=new int[nums.length+1][2];for(int i=l;i<=r;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);dp[i][1]=dp[i-1][0]+nums[i-1];}return Math.max(dp[r][0],dp[r][1]);}}

三、删除并获得点数

740. 删除并获得点数

题目描述：

题目分析：

这题看上去似乎与 “打家劫舍” 毫不相关。但仔细观察我们会发现，当选择值为 num[i] 的数字时， num[i] -1与 num[i] +1就无法被选中了。这与不能连续选择元素的 “打家劫舍” 问题不谋而合

我们可以创建一个hash数组，将 num[i] 的值映射到 hash数组对应的下标。然后再对hash数组进行一次 “打家劫舍” 即可

代码实现：

java">class Solution {public int deleteAndEarn(int[] nums) {int[] arr=new int[10001];for(int num:nums){arr[num]+=num;}int[] f=new int[10001],g=new int[10001];f[0]=arr[0];for(int i=1;i<10001;i++){f[i]=g[i-1]+arr[i];g[i]=Math.max(f[i-1],g[i-1]);}return Math.max(f[10000],g[10000]);}
}

四、粉刷房子

LCR 091. 粉刷房子

题目描述：

题目分析：

这个问题其实就是拓展版的 “打家劫舍” 问题。普通的 “打家劫舍” 问题每个状态只有选与不选两种，而该题有三种。但其实万变不离其中，仔细分析每种状态也能很好地做出来。

1、状态表示

用 r[i] 表示第 i 个位置选择红色时的最小花费
用 b[i] 表示第 i 个位置选择篮色时的最小花费
用 g[i] 表示第 i 个位置选择绿色时的最小花费

2、状态转移方程

由于每个位置都有三种选择，也就对应了三种状态：

对于 r[i] ：

如果第 i 个位置刷上红色，那么第 i-1 个位置上就只能刷蓝色或绿色。因此我们只需要知道第 i-1 个位置刷上蓝色或绿色这两种情况中的最小花费，再加上 i 位置的花费即可。可得状态转移方程就为：

r[i]=Math.min(b[i-1],g[i-1])+costs[i][0]

同理可以得出另外两种状态转移方程为：

b[i]=Math.min(r[i-1],g[i-1])+costs[i][1]
g[i]=Math.min(r[i-1],b[i-1])+costs[i][2]

4、初始化

为了避免 i-1 发生越界访问，我们可以先初始化当 i=0 时每种情况的初始值。而由于是首次选择，因此每组的最小花费就应该为对应的costs本身：

r[0]=costs[0][0]
b[0]=costs[0][1]
g[0]=costs[0][2]

代码实现：

java">class Solution {public int minCost(int[][] costs) {int n=costs.length;int[] r=new int[n],b=new int[n],g=new int[n];r[0]=costs[0][0];b[0]=costs[0][1];g[0]=costs[0][2];for(int i=1;i<n;i++){r[i]=Math.min(b[i-1],g[i-1])+costs[i][0];b[i]=Math.min(r[i-1],g[i-1])+costs[i][1];g[i]=Math.min(r[i-1],b[i-1])+costs[i][2];}return Math.min(r[n-1],Math.min(b[n-1],g[n-1]));}
}