【算法 动态规划 简单多状态 dp 问题】打家劫舍题型
打家劫舍题型
- 按摩师 (easy)
- 解题思路
- 代码
- 打家劫舍II （medium）
- 解题思路
- 代码
- 删除并获得点数（medium）
- 解题思路
- 代码
按摩师 (easy)
题目链接
该题是打家劫舍的变形
解题思路
- 状态表示
分析:
- 注意题目, 对于当天的预约, 可以接受, 也可以拒绝. 所以一天中有两个状态.
- 所以要定义两个状态, f[i] 和 g[i]
- f[i]: 表示, 在前 i 天中, 选择接受第 i 天的预约, 一共最长工作了多少时间
- g[i]: 表示, 在前 i 天中, 选择接受第 i 天的预约, 一共最长工作了多少时间
- 状态转移方程
状态转移图
依图可得
f[i] = g[i - 1] + nums[i - 1];g[i] = Math.max(f[i - 1],g[i - 1]);
- 初始化
不需要
- 填表顺序
根据「状态转移⽅程」得「从左往右，两个表⼀起填」。
- 返回值
return Math.max(f[n],g[n]);
代码
class Solution {public int massage(int[] nums) {int n = nums.length;int[] f = new int[n + 1]; // 表示选择 i, f[i] 总预约时间最长int[] g = new int[n + 1]; // 表示不选择ifor(int i = 1; i <= n; ++i) {f[i] = g[i - 1] + nums[i - 1];g[i] = Math.max(f[i - 1],g[i - 1]);}return Math.max(f[n],g[n]);}
}
打家劫舍II （medium）
题目链接
解题思路
环形问题想办法变成线性问题即可
- 对于 0 号位置, 有两种情况;
- 偷 0 号位置, 则 1 和 n -1 都不能偷了, 则对 [2,n-2] 进行一次打家劫舍即可
- 不偷, 则对 [1,n-1] 进行一次打家劫舍即可
返回这两种情况中的最大值即可
打家劫舍解法参考按摩师解题思路, 变的只是区间问题罢了
代码
class Solution {int n;public int rob(int[] nums) {n = nums.length;if(n == 0) return 0;if(n == 1) return nums[0];return Math.max(func(nums,2,n-2) + nums[0],func(nums,1,n-1));}public int func(int[] nums, int left, int right) {int[] f = new int[n];int[] g = new int[n];for(int i = left; i <= right; ++i) {f[i] = g[i - 1] + nums[i];g[i] = Math.max(f[i - 1], g[i - 1]);}return Math.max(f[right],g[right]);}
}
删除并获得点数（medium）
题目链接
解题思路
分析:
- 题目说获得 num[i] 的点数, 就要删除 num[i] -1 和 num[i] + 1 所有的值, 这就相当于偷 number 号房子, 就不能在偷 number -1 和 number + 1 号的房子
- 不同的是, 一个房子可以连续偷多次
- 题目给出的数据范围是 1 ~ 10000, 所以可以建立一个 int[] 类型的 hash, hash[i] 表示 i 在 num 数组中出现了多少次
- 这样就可以对 hash 数组, 从 1 ~ 10000 进行一次打家劫舍即可
代码
class Solution {int N = 10001;int[] hash = new int[N];public int deleteAndEarn(int[] nums) {for(int num : nums) {hash[num]++;} int[] f = new int[N];int[] g = new int[N];for(int i = 1; i < N; ++i) {f[i] = g[i - 1] + hash[i] * i;g[i] = Math.max(f[i - 1], g[i -1]);}return Math.max(f[N - 1], g[N - 1]);}
}