目录
一定要有这样的能力，碰到一个新题的时候，可以往之前做过的题方向靠！
打家劫舍问题模型: 不能选择相邻的两个数，并且要最终选择的数最大。
解决办法: 维护多个DP表，return 最值
- 后面的三个问题，其实都可以理解为是第一个题目的变形，例如说
- 对环形进行分情况，变为链形，抽离出DP 函数，使用两次
- 进行一个预处理，再 DP
- 两种情况变为多种情况
但是其实解决的思路都是一样的
1.面试题 17.16. 按摩师
链接： 面试题 17.16. 按摩师
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
示例 1：
输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。题解
- 圆圈表示预约，每个预约可以接或不接
- 不能接受相邻的预约
最优的预约集合（总预约时间最长），返回总的分钟数。
1.状态表示
- 经验 + 题目要求
dp[i] 表示：选择到 i 位置的时候，此时最长预约时长。
但是 i 位置可以选或者不选，因此继续细化
- f[i] 表示：选择到 i 位置的时候，nums[i] 必选，此时最长预约时长
- g[i] 表示：选择到 i 位置的时候，nums[i] 不选，此时最长预约时长
因为 这个位置的设置，是和上一个位置有关的
2.状态转移方程
- 依据 题目 所给的 相邻不能选规则
- f[i]=g[i-1]+nums[i] //选 i
- g[i]=max(f[i-1],g[i-1]) //不选 i
选的话 别忘记 i 位置的预约时长，然后相信 计算机就好啦
注释：
g[i] 表示 不选 i 位置，此时最长预约时长。 i 位置不选，那 i - 1 位置可选可不选，我们要找的是 0 ~ i - 1区间最长预约时长，有两种情况
- 选 i - 1 位置 ，而 f[i - 1] 表示必选 i - 1 位置此时最长预约时长，
- 不选 i - 1 位置，g[i - 1] 表示 不选 i - 1 位置此时最长预约时长
3.初始化
- 填表时不越界
这里我们也可以添加虚拟节点，但是这道题初始化太简单了，因此就不要添加虚拟节点。
填f[0]，g[0] 会越界，而f[0]表示必选0位置，g[0]表示不选0位置，因此
- f[0] = nums[0] ，g[0] = 0
4.填表
- 从左往右两个表一起填~
5.返回值
- 返回到达最后一个位置时最长预约时长
- max( f[n - 1]，g[n - 1] )
class Solution {
public:
int massage(vector<int>& nums)
{
//多状态dp
//f g
int n=nums.size();
if(n==0) return 0;
if(n==1) return nums[0];
//注意 边界处理
vector<int> f(n,0);
vector<int> g(n,0);
f[0]=nums[0];//选
for(int i=1;i<n;i++)
{
f[i]=g[i-1]+nums[i];
g[i]=max(g[i-1],f[i-1]);
}
return max(f[n-1],g[n-1]);
}
};if(n==0) return 0;
if(n==1) return nums[0];
//注意 边界处理
2.打家劫舍 II
- 打家劫舍：环形变种
链接： 213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。题解
- 这道题相比于打家劫舍I 多了这个条件：这个地方所有的房屋都 围成一圈
- 这意味着第一个房屋和最后一个房屋是紧挨着的，也就是说现在成了一个环路了。
同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
⭕分类讨论：
- 根据一个位置选or不选可以把问题从环形问题转化为线性问题
好好画下图，就可以想通啦
int rob(vector<int>& nums)
{
int n = nums.size();
//分类讨论两种情况下最大值
return max(dp(nums, 2, n-2) + nums[0], dp(nums, 1, n - 1));
}接下来是打家劫舍I的分析，和上面那道题几乎一模一样
1.状态表示
经验 + 题目要求
- f[i] 表示：偷到 i 位置的时候，偷 nums[i] ，此时的最大金额
- g[i] 表示：偷到 i 位置的时候，不偷 nums[i] ，此时的最大金额
2.状态转移方程
- f[i] = g[i-1] +nums[ i]
- g[i] =max( f[i-1],g[i-1])
3.初始化
- 填表时不越界
- f[0] = nums[0] ，g[0] = 0
4.填表
- 从左往右两个表一起填
5.返回值
- 返回偷到最后一个位置时最大金额
- max( f[n - 1]，g[n - 1] )
class Solution {
public:
int n;
int rob(vector<int>& nums)
{
n=nums.size();
if(n==0) return 0;
if(n==1) return nums[0];
if(n==2) return nums[0]>nums[1]?nums[0]:nums[1];
return max(dp(nums,1,n-1),dp(nums,2,n-2)+nums[0]);
//如何 实现 对环的处理的呢？
//通过 对第一个位置的 选 不选
//将dp 隔离为一个函数，两次调用~
}
int dp(vector<int>& nums,int begin,int end)
{
vector<int> f(n,0);
vector<int> g(n,0);
f[begin]=nums[begin];
for(int i=begin+1;i<=end;i++)
{
f[i]=g[i-1]+nums[i];
g[i]=max(g[i-1],f[i-1]);
}
return max(f[end],g[end]);
}
};return max(dp(nums,1),dp(nums,2)+nums[0]);
- 如何 实现 对环的处理的呢？
- 通过 对第一个位置的 选 不选
- 将dp 隔离为一个函数，两次调用~
3.删除并获得点数
- 打家劫舍：要预处理版
链接： 740. 删除并获得点数
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。题解
给你一个整数数组 nums ，你可以对它进行一些操作。
- 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。
- 之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
- 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
对于删除它并获得 nums[i] 的点数。
- 之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
- 删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素也就是说值等于这两个的数不能选了。
- 因此我们可以先对数组排一下序，方便找到 nums[i] - 1 和 nums[i] + 1 的 元素。
一定要有这样的能力，碰到一个新题的时候，可以往之前做过的题方向靠！
- 比如这道题如果是有序的并且中间数没有少，就像打家劫舍的问题。
- 比如说1、2、3、4、5。
- 选 1 之后不能选 2 了，是不是就是不能选择相邻的两个数，并且要最终选择的数最大。
所以如果说，数组是有序的话并且中间没有间隔，就是 “打家劫舍” 问题。
- 但是这里的数并不是那么连续的。如果中间数断了，就不是 “打家劫舍” 问题。
- 比如这里选 2 之后，还能选 4.
所以我们可以先用数组arr，把这些数先统计一下。
- 下标 i 表示这个数是几，arr[i] 表示 " i " 这个数出现的总和。
- 为什么预处理到数组中，因为 下标 i 是有序的。
- 然后就可以不要nums了，相当于在arr数组做一次 “打家劫舍” 。
比如说选了下标1里面的数，那下标 2 里面的数就不能要了，也就相当于选择当前这个数，相邻的数不能选了。可以选后面其他的数。
- 预处理：将数组中的数，统计到 arr 中，然后在 arr 中，做一次 “打家劫舍” 问题即可
1.状态表示
- 经验 + 题目要求
- f[i] 表示：选到 i 位置的时候， nums[i] 必选 ，此时能获得的最大点数
- g[i] 表示：偷到 i 位置的时候，nums[i] 不选，此时能获得的最大点数
2.状态转移方程
- f[i]=g[i-1]+arr[i]
- g[i]=max(f[i-1], g[i-1])
3.初始化
- 填表时不越界
- f[0] = arr[0] ，g[0] = 0
4.填表
- 从左往右
- 两个表一起填
5.返回值
- 返回偷到最后一个位置时最大金额
- max( f[n - 1]，g[n - 1] )
class Solution {
public:
int deleteAndEarn(vector<int>& nums)
{
sort(nums.begin(),nums.end());
int n=nums.size();
if(n==0) return 0;
if(n==1) return nums[0];
vector<int> arr(10001,0);
//预处理 建立映射
for (auto num : nums)
{
arr[num] += num;
}
//dp 无需管空值，还是和以前一样就行~
int m=arr.size();
vector<int> f(m,0);
vector<int> g(m,0);
f[0]=arr[0];
for(int i=1;i<m;i++)
{
f[i]=g[i-1]+arr[i];
g[i]=max(g[i-1],f[i-1]);
}
return max(f[m-1],g[m-1]);
}
};dp 无需管 arr 空值，还是和以前一样就行~
- int m=arr.size();
- vector<int> f(m,0);
4.粉刷房子
- 打家劫舍：选择 两种变三种
链接： LCR 091. 粉刷房子
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。
示例 1：
输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
最少花费: 2 + 5 + 3 = 10。题解
- 有n个房子，每个房子都可以被粉刷成红色，蓝色，绿色，相邻的房子颜色不能相同。
- 每个房子粉刷成不同颜色的价格由一个3*n的矩阵给出，左边0 ~ 2表示房子，上面0 ~ 2表示每个房子被粉刷不能颜色的价格。
要找到粉刷完所有房子最少的价格。
这不是 刚好符合 我们打家劫舍的两个模型特征了 吗~
1.状态表示
- 经验 + 题目要求
以 i 位置为结尾，当涂到 i 位置的时候此时的最小花费，但是涂到 i 位置还可以细分，涂成红色，蓝色，绿色。
- dp[i][0] 表示：粉刷到 i 位置的时候，最后一个位置粉刷上 红色，此时的最小花费
- dp[i][1] 表示：粉刷到 i 位置的时候，最后一个位置粉刷上 蓝色，此时的最小花费
- dp[i][2] 表示：粉刷到 i 位置的时候，最后一个位置粉刷上 绿色，此时的最小花费
对比 打家劫舍的两种选不选，这里是有三种选择的可能
也可以这么理解
- f[i] == dp[i][0]
- g[i] == dp[i][1]
所以有 四种 五种可能，我们也是这么处理
2.状态转移方程
此时分三种情况讨论：
- 如果 i 位置涂成红色这个位置花费已经固定了 cost[i][0]，我要的是最小花费，只要保证 0 ~ i -1 区间花费最小就行了。
- 涂到 i - 1 位置只能涂成蓝色、绿色，dp[i-1][1]表示涂到 i - 1 位置涂蓝色此时最小花费，dp[i-1][2]表示涂到 i - 1 位置涂绿色此时最小花费
- 因此 i 位置涂成红色状态转移方程就处理了，剩下也是这样的处理：
3.初始化
- 填表时不越界
这里我们可以多申请一个空间。这样就可以把初始化放到填表里面了。但是要注意两点：
- 虚拟节点里面的值，要保证后序填表时正确的
- 下标的映射关系
首先看虚拟节点里面的值应该填多少
- 可以先考虑没有虚拟节点第一个位置应该填多少，是不是填的是自己本身啊，因此虚拟节点里面的值我们给0。
- 因为我们多开一个空间，相当于整体向右移一位，如果要回去矩阵 下标应该减 1。
4.填表
- 从左往右三个表一起填
5.返回值
- 返回涂到最后一个位置，涂成红，蓝，绿最小花费
- 多状态，就每个状态 都维护一个DP表min（dp[n][0]，dp[n][1]，dp[n][2]）
class Solution {
public:
int minCost(vector<vector<int>>& costs)
{
int n=costs.size();
vector<vector<int>> dp(n+1,vector<int>(3,0));
for(int i=1;i<=n;i++)
{
dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];
dp[i][1]=min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];
dp[i][2]=min(dp[i-1][0],dp[i-1][1])+costs[i-1][2];
//注意 下表映射
}
return min(dp[n][0],min(dp[n][1],dp[n][2]));
//对填完了的表 ，进行选择
}
};多状态，就每个状态 都维护一个DP表
空间换时间！！！！！！