简朴多状态dp问题 + 总结（一）
按摩师标题链接
https://i-blog.csdnimg.cn/direct/79b2c2ea4cb940c6b029b3b9a6a671bd.png
题解
1. 细节处理：标题是有没有客人的时间，所有n便是零时返回零
2. 状态表现：到达i位置时的最长预约时长
3. 状态转移方程：到达i位置的时间分为选或者不选，选的话，前一个位置就是不选，不选的话，前一个位置可以是不选或者是选中的最大值
https://i-blog.csdnimg.cn/direct/e38c7d9362da4b1886304eaae5b7fc8d.png
代码
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 = nums;
for(int i = 1;i < n;i++)
{
f = g + nums;
g = max(f,g);
}
return max(g,f);
}
};
打家劫舍II
标题链接
https://i-blog.csdnimg.cn/direct/5bc478a9485b4a688a61ca43e514b382.png
题解
1. 这题的思路和按摩师几乎一模一样，只不外可以分为第一个位置偷和第一个位置不偷的环境，末了比力两种环境哪种的金额最大
2. 第一个位置偷的环境，那么末了一个位置和第二个位置都不能偷，在内进行一次按摩师
第一个位置不偷的环境，在区间内进行一次按摩师
https://i-blog.csdnimg.cn/direct/0349fa7f982645e7ba85cbff4336b7d8.png
代码
class Solution
{
public:
int rob(vector<int>& nums)
{
int n = nums.size();
if(n == 0) return 0;
if(n == 1)
{
return nums;
}
if(n == 2)
{
return nums > nums ? nums : nums;
}
vector<int> f(n);// 最后一个位置偷
vector<int> g(n);// 最后一个位置不偷
f = nums,g = 0;
int x = 0,y = 0;
// 第一个位置偷
for(int i = 3;i < n-1;i++)
{
f = g + nums;
g = max(g,f);
}
x = nums + max(f,g);
// 第一个位置不偷
f = nums,g = 0;
for(int i = 2;i < n;i++)
{
f = g + nums;
g = max(g,f);
}
y = max(f,g);
return max(x,y);
}
};
删除并获得点数
标题链接
https://i-blog.csdnimg.cn/direct/e639abccbbc04c82b276c552fe12c83f.png
题解
1. 可以先将数组预处理为下标对应的数的所有和相加，这样可以转换为打家劫舍问题，排序后选了一个数，相邻的两个数不能选
2. 这样arr数组就可以写成打家劫舍问题的代码了
https://i-blog.csdnimg.cn/direct/d1daab60dfe0409fa9c0ef017b2d037d.png
代码
class Solution
{
public:
int arr;
int deleteAndEarn(vector<int>& nums)
{
// 怎么达到不遍历可以删除其他数达到最大值呢？
// 可以转化为自己熟悉的打家劫舍问题
int n = nums.size();
int ans = 0;
for(int i = 0;i < n;i++)
{
arr] += nums;
ans = max(ans,nums);
}
if(n == 0) return 0;
vector<int> f(ans+1);
vector<int> g(ans+1);
f = arr,g = 0;
for(int i = 1;i <= ans;i++)
{
f = g + arr;
g = max(f,g);
}
return max(f,g);
}
};
粉刷房子
标题链接
https://i-blog.csdnimg.cn/direct/c5a71873cc8c4f64949b5cc6560a1bd3.png
题解
1. 红色是0，绿色是1，蓝色是2
2. 可以分解为3个一维的线性dp，末了一个位置选红色，那么前一个位置的状态是选绿色和黄色中的最小值
3. 同时填表，有三种颜色，n个房子，按线性dp的模式写
https://i-blog.csdnimg.cn/direct/a228d8ba74414562bb54251ef618c0cc.png
代码
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 = min(dp,dp) + costs;
dp = min(dp,dp) + costs;
dp = min(dp,dp) + costs;
}
return min(min(dp,dp),dp);
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]