[dp5_多状态dp] 按摩师 | 打家劫舍 II | 删除并获得点数 | 粉刷房子

目录

1.面试题 17.16. 按摩师

题解

2.打家劫舍 II

题解

3.删除并获得点数

题解

4.粉刷房子

题解

---

一定要有这样的能力，碰到一个新题的时候，可以往之前做过的题方向靠！

打家劫舍问题模型:  不能选择相邻的两个数，并且要最终选择的数最大。
解决办法:  维护多个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  gint 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表

空间换时间！！！！！！