简单多状态dp问题 + 总结（一）

按摩师

题目链接

题解

1. 细节处理：题目是有没有客人的时候，所有n等于零时返回零
2. 状态表示：到达i位置时的最长预约时长
3. 状态转移方程：到达i位置的时候分为选或者不选，选的话，前一个位置就是不选，不选的话，前一个位置可以是不选或者是选中的最大值

代码

class Solution 
{
public:int massage(vector<int>& nums) {int n = nums.size();if(n == 0) return 0;// 空数组是没有预约时间的vector<int> f(n);// 最后一个状态选vector<int> g(n);// 最后一个状态不选f[0] = nums[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(g[n-1],f[n-1]);}
};

打家劫舍II

题目链接

题解

1. 这题的思路和按摩师几乎一模一样，只不过可以分为第一个位置偷和第一个位置不偷的情况，最后比较两种情况哪种的金额最大
2. 第一个位置偷的情况，那么最后一个位置和第二个位置都不能偷，在[2，n-2]内进行一次按摩师
第一个位置不偷的情况，在[1，n-1]区间内进行一次按摩师

代码

class Solution 
{
public:int rob(vector<int>& nums) {int 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];}vector<int> f(n);// 最后一个位置偷vector<int> g(n);// 最后一个位置不偷f[2] = nums[2],g[2] = 0;int x = 0,y = 0; // 第一个位置偷for(int i = 3;i < n-1;i++){f[i] = g[i-1] + nums[i];g[i] = max(g[i-1],f[i-1]);}x = nums[0] + max(f[n-2],g[n-2]);// 第一个位置不偷f[1] = nums[1],g[1] = 0;for(int i = 2;i < n;i++){f[i] = g[i-1] + nums[i];g[i] = max(g[i-1],f[i-1]);}y = max(f[n-1],g[n-1]);return max(x,y);}
};

删除并获得点数

题目链接

题解

1. 可以先将数组预处理为下标对应的数的所有和相加，这样可以转换为打家劫舍问题，排序后选了一个数，相邻的两个数不能选
2. 这样arr数组就可以写成打家劫舍问题的代码了

代码

class Solution 
{
public:int arr[10001];int deleteAndEarn(vector<int>& nums) {// 怎么达到不遍历可以删除其他数达到最大值呢？// 可以转化为自己熟悉的打家劫舍问题int n = nums.size();int ans = 0;for(int i = 0;i < n;i++){arr[nums[i]] += nums[i];ans = max(ans,nums[i]);}if(n == 0) return 0;vector<int> f(ans+1);vector<int> g(ans+1);f[0] = arr[0],g[0] = 0;for(int i = 1;i <= ans;i++){f[i] = g[i-1] + arr[i];g[i] = max(f[i-1],g[i-1]);}return max(f[ans],g[ans]);}
};

粉刷房子

题目链接

题解

1. 红色是0，绿色是1，蓝色是2
2. 可以分解为3个一维的线性dp，最后一个位置选红色，那么前一个位置的状态是选绿色和黄色中的最小值
3. 同时填表，有三种颜色，n个房子，按线性dp的模式写

代码

class Solution
{
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();vector<vector<int>> dp(n+1,vector<int>(3));// 0红 1绿 2蓝for(int i = 1;i < n+1;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][1],dp[i-1][0]) + costs[i-1][2];}return min(min(dp[n][0],dp[n][1]),dp[n][2]);}
};

总结

1. 多状态一般可以分为三种状态
2. 分析出状态表示基本上就很好些了
3. 状态转移方程为三个线性的dp，分析前一个转态，填写现在这个状态