动态规划4,打家劫舍问题,删除并获得点数
打家劫舍I
思路:
- 经验+题目要求
dp[i]表示:选择到 i 位置时候,偷窃到的最高金额。
继续细化:
f[i]表示:选择到i位置时候,nums[i]必选,此时的最高金额。
g[i]表示:选择到i位置时候,nums[i]不选,此时的最高金额。
如果 i 位置偷,那么i-1就不能偷,此时就是f[i] = g[i-1] + nums[i];
如果 i 位置不偷,那么i-1就有两种情况,可以偷也可以不偷, 偷的话就是g[i] = f[i-1];不偷的话就是 g[i] = g[i-1];
选出他们的最大值,就有了g[i] = max(f[i-1],g[i-1]);
3.f[0]表示0位置必偷,所以是nums[0]; g[0]不偷所以是0。
4.从左向右,两个表一块填写。
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> f(n);//选
vector<int> g(n);//不选
f[0] = nums[0];
g[0] = 0;
for(int i = 1; i<n; i++)
{
f[i] = nums[i] + g[i-1];
g[i] = max(f[i-1],g[i-1]);
}
return max(f[n-1],g[n-1]);
}
};
打家劫舍II
思路:
变成环形了,可以理解为头就是尾,可以对头分析:
如果第一个位置偷的话,第二个位置和最后一个位置不能偷,实际上就是从2 ~ n-2 进行打家劫舍I。
如果第一个位置不偷,就变成了从 1 ~ n-1 进行打家劫舍I。
- 经验+题目要求
dp[i]表示:选择到 i 位置时候,偷窃到的最高金额。
继续细化:
f[i]表示:选择到i位置时候,nums[i]必选,此时的最高金额。
g[i]表示:选择到i位置时候,nums[i]不选,此时的最高金额。
如果 i 位置偷,那么i-1就不能偷,此时就是f[i] = g[i-1] + nums[i];
如果 i 位置不偷,那么i-1就有两种情况,可以偷也可以不偷, 偷的话就是g[i] = f[i-1];不偷的话就是 g[i] = g[i-1];
选出他们的最大值,就有了g[i] = max(f[i-1],g[i-1]);
3.f[0]表示0位置必偷,所以是nums[0]; g[0]不偷所以是0。
4.从左向右,两个表一块填写。
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
//1.第一个位置选和2 ~ n-2
//2.第一个位置不选:1 ~ n-1
return max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));
}
int rob1(vector<int>&nums,int begin,int end)//打家劫舍I
{
if(begin > end) return 0;//防止n = 1的情况
int n = nums.size();
vector<int> f(n);
vector<int> g(n);
f[begin] = nums[begin];
g[begin] = 0;
for(int i = begin+1; i<=end; i++)
{
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1],g[i-1]);
}
return max(f[end],g[end]);
}
};
删除并获得点数
思路:
仔细看,删除 nums[i] 的点数之后,要删除所有等于 nums[i] - 1 和 nums[i] - 2的元素,是不是很像打家劫舍问题,不能连续偷,我们来想办法变成打家劫舍问题,进行预处理:
将数组中的数,统计到arr中,然后对arr数组,做一次 打家劫舍 问题即可。
- 经验+题目要求
dp[i]表示:选择到 i 位置时候,偷窃到的最高金额。
继续细化:
f[i]表示:选择到i位置时候,nums[i]必选,此时的最高金额。
g[i]表示:选择到i位置时候,nums[i]不选,此时的最高金额。
如果 i 位置偷,那么i-1就不能偷,此时就是f[i] = g[i-1] + nums[i];
如果 i 位置不偷,那么i-1就有两种情况,可以偷也可以不偷, 偷的话就是g[i] = f[i-1];不偷的话就是 g[i] = g[i-1];
选出他们的最大值,就有了g[i] = max(f[i-1],g[i-1]);
3.f[0]表示0位置必偷,所以是nums[0]; g[0]不偷所以是0。
4.从左向右,两个表一块填写。
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int arr[10001] = {0};
for(auto s : nums)
{
arr[s] += s;
}
vector<int> f(10001);
auto g = f;
f[0] = arr[0];
g[0] = 0;
for(int i = 1; i<10001; i++)
{
f[i] = g[i-1] + arr[i];
g[i] = max(g[i-1],f[i-1]);
}
return max(f[10000],g[10000]);
}
};
原文地址:https://blog.csdn.net/weixin_74461263/article/details/136329468
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!