164、【动态规划】leetcode ——213. 打家劫舍 II:环形列表线性化(C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接:213. 打家劫舍 II
解题思路
本题与 198. 打家劫舍(动态规划) 的区别在于,此次的要求为环形列表,而198里的是线性链表。对于环形链表的解题思路是将环形进行线性化,分情况进行讨论。
例如,对nums = [1,2,3,4,1]
- 情况一:范围在[2,3,4]中进行选择
- 情况二:范围在[1,2,3,4]中进行选择
- 情况三:范围在[2,3,4,1]中进行选择
可以发现,情况二和三会包含情况一,因此我们只需分别求情况二和情况三,得到的最大情况,然后再对二者取最大值,即可。
class Solution {
public:
int robRange(vector<int>& nums, int start, int end) {
if(start == end) return nums[start];
int dp[101] = {0};
dp[start] = nums[start];
dp[start + 1] = max(nums[start], nums[start + 1]);
for(int i = start + 2; i <= end; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[end];
}
int rob(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
int dp1 = robRange(nums, 0, nums.size() - 2);
int dp2 = robRange(nums, 1, nums.size() - 1);
return max(dp1, dp2);
}
};
参考文章:213. 打家劫舍 II
另一写法
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
if(nums.size() == 2) return max(nums[0], nums[1]);
int n = nums.size();
vector<int> dp1(n);
vector<int> dp2(n);
dp1[0] = nums[0], dp1[1] = max(nums[0], nums[1]);
dp2[0] = nums[1], dp2[1] = max(nums[1], nums[2]);
for(int i = 2; i < n - 1; i++) {
dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
}
for(int i = 3; i < n; i++) {
dp2[i - 1] = max(dp2[i - 2], dp2[i - 3] + nums[i]);
}
// 因为各自只有n-1个数
return max(dp1[n - 2], dp2[n - 2]);
}
};
相关文章
- vc++木马源码免杀一些常用方法
- leetcode 10 正则表达式匹配(c++)
- 二分查找法的C++泛型实现
- C++整数转二进制
- paddle 44 用onnxruntime实现ppyoloe模型的部署(含python和c++版本),支持batchsize
- Bitmap 图片格式并用 C++ 读写 Bitmap
- 最好的 C++ 模板元编程干货!
- Leetcode 两数之和 C / C++
- C++ vector容器resize之后再push_back
- [LeetCode] 032. Longest Valid Parentheses (Hard) (C++)
- 8.2 C++ AMP advanced concepts
- AI模型C++部署:ubuntu安装Cython并使用C/C++调用python动态库【附加c++与python互相调用算法demo程序接口的源码】
- C++ >>和<<读写文本文件
- VS2019: C++代码静态分析改进和更新
- vs2019编写c++的静态链接库并自己使用
- c++高精加模板
- 【高级C】GNU C/C++ 内联汇编——实例参考
- 【C++ 科学计算】C++ 矩阵操作运算符
- 【图像处理OpenCV(C++版)】——初学OpenCV