C++算法第十二天
本篇文章，我们继续学习动态规划
第一题
题目链接
面试题 17.16. 按摩师 - 力扣（LeetCode）
题目解析
代码原理
代码编写
细节问题处理
这里的细节问题就是当n == 0时的这种情况
完整源代码
class Solution {
public:
int massage(vector<int>& nums) {
int n = nums.size();
//细节处理
if(n == 0)
return n;
//建表
vector<int> f(n), g(n);
//初始化
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(g[n - 1], f[n - 1]);
}
};
第二题
题目链接
213. 打家劫舍 II - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
int sloutionway(vector<int>& nums,int left,int right)
{
if(left > right) return 0;
int n = nums.size();
//建表
vector<int>f(n),g(n);
//初始化
f[left] = nums[left];
//填表
for(int i = left + 1; i <= right; i++)
{
f[i] = g[i - 1] + nums[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[right], g[right]);
}
int rob(vector<int>& nums) {
int n = nums.size();
return max(sloutionway(nums, 1, n - 1), nums[0] + sloutionway(nums, 2, n - 2));
}
};
第三题
题目链接
740. 删除并获得点数 - 力扣（LeetCode）
题目解析
下面的示例二也是一样的道理，总结一下还是选和不选的问题，只不过只有第一次删除才获得点数，后面删除的cur[i] + 1和cur[i] - 1都不加点数
代码原理
代码编写
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
const int N = 10001;
//数组预处理
int arr[N] = {0};
for(auto cur: nums) arr[cur] += cur;
//建表
vector<int> f(N),g(N);
//初始化
f[0] = arr[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]);
}
};
本题总结
遇到与《选和不选》相关且数字有序（无序）有可能还是数字不连续的，需要先预处理一下原先的数组，之后在预处理好的新数组里面进行一次打家劫舍问题即可。
本篇文章的内容就先到这里，我们下期文章再见。
记得一键三联哦！！！
