【动态规划】简单多状态 dp 问题
简单多状态 dp 问题
- 1.面试题 17.16. 按摩师
- 2.打家劫舍 II
- 3.删除并获得点数
- 4.粉刷房子
- 4.买卖股票的最佳时机含冷冻期
- 5.买卖股票的最佳时机含手续费
- 6.买卖股票的最佳时机 III
- 7.买卖股票的最佳时机 IV
点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃
1.面试题 17.16. 按摩师
题目链接： 面试题 17.16. 按摩师
题目分析：
圆圈表示预约，每个预约可以接或不接，不能接受相邻的预约，最优的预约集合（总预约时间最长），返回总的分钟数。
算法原理：
1.状态表示
经验 + 题目要求
dp[i] 表示：选择到 i 位置的时候，此时最长预约时长。
但是 i 位置可以选或者不选，因此继续细化
f[i] 表示：选择到 i 位置的时候，nums[i] 必选，此时最长预约时长
g[i] 表示：选择到 i 位置的时候，nums[i] 不选，此时最长预约时长
2.状态转移方程
f[i] 表示 必选 i 位置，此时最长预约时长。i 位置可以选，那 i - 1 位置就不能选了，而我们想要的是最长预约时长，那就把 0 ~ i- 1 区间内最长预约时长给我，这个最长预约时长保证 i - 1 位置必不选。而 g[i-1] 表示 i -1位置不选此时最长预约时长。当然也别忘记 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) { // 1.创建dp表 // 2.初始化 // 3.填表 // 4.返回值 int n = nums.size(); if(n == 0) return 0;//处理边界情况 vector<int> fdp(n); vector<int> gdp(n); fdp[0] = nums[0], gdp[0] = 0; for(int i = 1; i < n; ++i) { fdp[i] = gdp[i - 1] + nums[i]; gdp[i] = max(fdp[i - 1],gdp[i - 1]); } return max(fdp[n - 1], gdp[n - 1]); }};2.打家劫舍 II
题目链接： 213. 打家劫舍 II
题目分析：
这道题相比于打家劫舍I 多了这个条件：这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的，也就是说现在成了一个环路了。
同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
算法原理：
分类讨论：
根据第一个位置选or不选可以把问题从环形问题转化为线性问题
接下来是打家劫舍I的分析，和上面那道题几乎一模一样
1.状态表示
经验 + 题目要求
f[i] 表示：偷到 i 位置的时候，偷 nums[i] ，此时的最大金额
g[i] 表示：偷到 i 位置的时候，不偷 nums[i] ，此时的最大金额
2.状态转移方程
3.初始化
填表时不越界
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(dp(nums, 2, n-2) + nums[0], dp(nums, 1, n - 1)); } int dp(vector<int>& nums, int left, int right) { if(left > right) return 0; // 1.创建 dp 表 // 2.初始化 // 3.填表 // 4.返回值 int n = nums.size(); vector<int> f(n); vector<int> g(n); f[left] = nums[left], g[left] = 0; for(int i = left + 1; i <= right; ++i) { f[i] = g[i - 1] + nums[i]; g[i] = max(f[i - 1
