C++简单多状态dp：按摩师、打家劫舍II、删除并获得点数、粉刷房子
目录
按摩师：
打家劫舍II：
删除并获得点数：
粉刷房子：
按摩师：
题目链接：面试题 17.16. 按摩师 - 力扣（LeetCode）
题目要求：
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
题目分析：
首先来看一下题目要求，可以简化为给你一个数组，让你选数，然后给定一个要求(不能选择相邻的两个数)，让你求出一个最大值。这里要注意一个点，就是虽然数组的数相邻的不能连续选，但是相邻的我可以连续不选，就比如示例3中，倒数第2和第3个数是相邻的，但是这两个数我可以都不选，然后选倒数第一个数。收集完题目信息后就可以使用动态规划的五步法了：
1、状态表示：
从题目和示例我们可以得知，这是一个从左往右推导的模型题，这种题目一般就是根据经验和题目要求来求解了，经验就是：该题是以某一个位置为结尾，然后……的这种题目。
此时可以定义为：dp[i] 表示：选择到 i 位置的时候，此时的最长预约时长（也就是最大值）
关于这个状态表示又可以细划分为两个子状态：也就是到dp[i] 位置时，我选择该位置的值(后面用 f 来表示) 和 我不选择该位置的值(后面用 g 来表示)：假设给的数组为nums：
f[i] 表示：选择到 i 位置时，选上nums[i]，此时的最大数值。
g[i] 表示：选择到 i 位置时，不选nums[i]，此时的最大数值。
2、状态转移方程：
3、初始化：
因为会涉及到 -1 的位置，所以要初始化0这个位置防止越界，也就是要对f[0]、g[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) {
int n = nums.size();
// 处理特殊情况(空数组):
if(n == 0) return 0;
// 建表:
vector<int> f(n);
auto g = f;
// 初始化f[0],g[0]:
f[0] = nums[0];
g[0] = 0;
for(int i = 1; i < n; i++)
{
// 填表:
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1],g[i-1]);
}
return max(f[n-1],g[n-1]);
}
};
打家劫舍II：
题目链接：LCR 090. 打家劫舍 II - 力扣（LeetCode）
题目要求：
一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
题目分析：
该题可以简化为给你一个数组，让你选数，然后给定一个要求(不能选择相邻的两个数)，让你求出一个最大值。分析题目可知：虽然数组的数相邻的不能连续选，但是相邻的我可以连续不选，同时还要注意一个细节：题目指出数组是一个环形，收尾相连的，也就是第一个和最后一个数看作是相邻的，也不能同时选。
打家劫舍1题目链接：LCR 089. 打家劫舍 - 力扣（LeetCode）
打家劫舍1和按摩师的解题思路是一样的。
1、状态表示：
按照上面的题目分析可得该题的状态表示有两个，就是到 i 位置时，是选择偷还是不偷，此时可获取的最大金额（也就是最大值），分别用 f[i] 和 g[i] 表示：
f[i] 表示：偷到 i 位置时，偷nums[i]，此时的最大金额
g[i] 表示：偷到 i 位置时，不偷nums[i]，此时的最大金额
2、状态转移方程：
f[i] 表示到 nums[i] 位置时必偷，那么 nums[i - 1] 位置是必不偷的，nums[i - 1] 位置的最大值也就是 g[i - 1]，所以 f[i] 的方程为：f[i] = g[i - 1] + nums[i]；
g[i] 表示到nums[i] 位置时必不偷，但注意是nums[i - 1]位置是可偷可不偷的，所以 g[i] 有两种情况：
nums[i - 1] 位置偷，那么g[i] = f[i - 1]
nums[i - 1] 位置不偷，那么g[i] = g[i - 1]
但是 g[i] 我们只要最大的值，所以 g[i] 的方程为：g[i] = max( f[i - 1] ，g[i - 1] )；
3、初始化：
因为会涉及到 -1 的位置，所以要初始化0这个位置防止越界，也就是要对f[0]、g[0] 这两个位置进行初始化，根据状态转移方程推出：f[0] = nums[0]，g[0] = 0。
4、填表顺序：从左往右推导模型，填表顺序也就是两个表同时从左往右填了。
5、返回值：返回两个表中最后一个位置的最大值即可，也就是：max( f[n-1]，g[n-1] )。
题解代码：
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
// 两种情况下的最大值(选第一个和不选第一个)
return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
}
// rob1就是打家劫舍1的思路
int rob1(vector<int>& nums, int l, int r) {
if (l > r)
return 0;
int n = nums.size();
vector<int> f(n);
auto g = f;
// 初始化
f[l] = nums[l];
g[l] = 0;
for (int i = l + 1; i <= r; i++) {
f[i] = g[i - 1] + nums[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[r], g[r]);
}
};
删除并获得点数：
题目链接：740. 删除并获得点数 - 力扣（LeetCode）
题目要求：
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
题目分析：
仔细看这个题目是不是有点像打家劫舍系列的题目？就是一个数相邻的左右无法选，例如选了2，就不能选1和3，选了4就不能选3和5，只是实际情况复杂了一点，选择的那个数可能在nums中出现多次(也就是需要累加)，以及选择的数它的相邻数并不一定出现在nums数组中，那么可以根据这些设定简化成打家劫舍系列的题目：
1、状态表示：
根据上面的题目分析，我们先对给出的数组进行一次预处理，也就是将数组中的数统计到arr中，然后再对arr进行一次"打家劫舍1"的解题即可，那么这题的状态表示也就跟打家劫舍1一样了。
此时就转变为了对arr数组进行分析：该题的状态表示有两个，就是到 i 位置时，是选还是不选，此时可获取的最大点数，分别用 f[i] 和 g[i] 表示：
f[i] 表示：到 i 位置时，必选arr[i]，此时可获得的最大点数
g[i] 表示：到 i 位置时，不偷arr[i]，此时可获得的最大点数
2、状态转移方程：
f[i] 表示到 arr[i] 位置时必选，那么 arr[i - 1] 位置是必不选的，arr[i - 1] 位置的最大值也就是 g[i - 1]，所以 f[i] 的方程为：f[i] = g[i - 1] + arr[i]；
g[i] 表示到 arr[i] 位置时必不选，但注意是arr[i - 1]位置是可选可不选的，所以 g[i] 有两种情况：
arr[i - 1] 位置选，那么g[i] = f[i - 1]
arr[i - 1] 位置不选，那么g[i] = g[i - 1]
但是 g[i] 我们只要最大的值，所以 g[i] 的方程为：g[i] = max( f[i - 1] ，g[i - 1] )；
3、初始化：
初始化是为了防止填表越界的情况发生，根据状态转移方程的-1来看，0位置时可能会发生越界，所以要初始化 f[0] 和 g[0] 这两个位置。根据状态转移方程推出：f[0] = arr[0]，g[0] = 0。
4、填表顺序：从左往右推导模型，填表顺序也就是两个表同时从左往右填了。
5：返回值：返回两个表中最后一个位置的最大值即可，也就是：max( f[n-1]，g[n-1] )。
题解代码：
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
// 最主要的是预处理这一步工作，处理完就是完全的打家劫舍问题了：
// 预处理：
auto a = nums;
sort(a.begin(), a.end());
int n = *(a.end() - 1) + 1; // 找出nums中的最大的那个数，用于开空间
vector<int> arr(n);
for(auto x : nums) arr[x] += x; // 映射处理
// 处理完后就是打家劫舍1的解题了：
vector<int> f(n);
auto g = f;
f[0] = arr[0];
g[0] = 0;
for(int i = 1; i < n; i++)
{
f[i] = g[i - 1] + arr[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[n - 1], g[n - 1]);
}
};
粉刷房子：
题目链接：LCR 091. 粉刷房子 - 力扣（LeetCode）
题目要求：
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。
题目分析：
1、状态表示：
这类题如果简化一下就可以发现还是可以简化成打家劫舍1类的题目，其实本质就是个一维数组，就是一排房子，相邻两个不可以同色，求到 i 位置的最小花费，也就是 dp[i]，根据 i 房子的颜色又可以细化为三种状态：为了方便表示，这里使用二维数组，并使用012代表红蓝绿三种颜色：
dp[i][0] 表示：粉刷到 i 位置时，i 位置粉刷上 红色，此时的最小花费。
dp[i][1] 表示：粉刷到 i 位置时，i 位置粉刷上 蓝色，此时的最小花费。
dp[i][2] 表示：粉刷到 i 位置时，i 位置粉刷上 绿色，此时的最小花费。
2、状态转移方程：
因为相邻房屋无法同色的问题，所以(拿红色举例)当 i 位置粉刷上红色时，前一个房屋必定是蓝色或者绿色（取其中最小花费），然后再加上 i 位置的红色的花费就是 dp[i][0] 的花费，（蓝色和绿色同理）所以三种状态的方程为：
红色：dp[i][0] = min( dp[i - 1][1]，dp[i - 1][2] ) + costs[i][0]
蓝色：dp[i][1] = min( dp[i - 1][0]，dp[i - 1][2] ) + costs[i][1]
绿色：dp[i][2] = min( dp[i - 1][0]，dp[i - 1][1] ) + costs[i][2]
3、初始化：
因为状态转移方程会涉及到-1，也就是0的位置要注意越界问题，所以我们可以往前开一个虚拟节点代替原来下标为0的位置，然后初始化为0，因为当0个房子要粉刷的时候，自然花费为0，然后就可以顺序往下填表了。所以dp[0][0]、dp[0][1]、dp[0][2]位置的值都为0。
4、填表顺序：
从左往右推导模型（也就是往后填时要确保前面的数是填好了的），所以填表顺序是三个表（二维数组中的三行）同时从左往右填。
5、返回值：返回三个表（二维数组中的三行）的最小值（最小花费）。
题解代码：
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int n = costs.size();
// n + 1：增加虚拟节点
vector<vector<int>> dp(n + 1, vector<int>(3));
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]));
}
};