Day 48 动态规划
198. 打家劫舍
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++)
{
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp.back();
}
};
213. 打家劫舍II
分成两段来处理:比如说输入的长度是n(0~n-1),就分成[0, n - 1)和[1, n)两部分文章来源:https://www.toymoban.com/news/detail-604166.html
class Solution {
int robSeg(const vector<int> &nums, int left, int right)
{
int len = right - left;
if (len == 0) return 0;
if (len == 1) return nums[left];
vector<int> dp(len, 0);
dp[0] = nums[left];
dp[1] = max(nums[left], nums[left + 1]);
for (int i = 2; i < dp.size(); i++)
{
dp[i] = max(dp[i - 2] + nums[left + i], dp[i - 1]);
}
return dp.back();
}
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (len == 0) return 0;
if (len == 1) return nums[0];
return max(robSeg(nums, 0, len - 1), robSeg(nums, 1, len));
}
};
337. 打家劫舍III
写一个辅助函数,返回两个状态,抢或者不抢能得到的最大收获。文章来源地址https://www.toymoban.com/news/detail-604166.html
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
vector<int> robTree(TreeNode *root)
{
if (!root) return {0, 0}; // {rob, not rob}
auto leftRet = robTree(root->left);
auto rightRet = robTree(root->right);
int sumRob = root->val + leftRet[1] + rightRet[1];
// int sumNotRob = leftRet[0] + rightRet[0]; // 不偷不是这样写的
int sumNotRob = max(leftRet[0], leftRet[1]) + max(rightRet[0], rightRet[1]);
return {sumRob, sumNotRob};
}
public:
int rob(TreeNode* root) {
auto ret = robTree(root);
return max(ret[0], ret[1]);
}
};
到了这里,关于算法刷题Day 48 打家劫舍+打家劫舍II+打家劫舍III的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!