LC198. 打家劫舍
自己写的版本,用pair<不取本次的最大收获, 取本次的最大收获>进行记录
int rob(vector<int>& nums)
{
int size = nums.size();
vector<pair<int, int>> dp(size);
dp[0] = pair<int, int>(0, nums[0]);
for (int i = 1; i < size; ++i)
{
dp[i].first = max(dp[i - 1].first, dp[i - 1].second);
dp[i].second = dp[i - 1].first + nums[i];
}
return max(dp[size - 1].first, dp[size - 1].second);
}
Carl哥版本
int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
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[nums.size() - 1];
}
LC213. 打家劫舍Ⅱ
想到之前“分糖果”的左右规则,要从两个维度去考虑。
所以就想下,第一次遍历,只考虑从第一个元素到倒数第二个元素(第一个元素可能被选,也可能不被选,但最后一个元素一定不被选)。那为了避免最后一个元素一定不被选的情况,只考虑从第二个元素到最后一个元素。
int rob(vector<int>& nums)
{
int size = nums.size();
if (size == 1)
{
return nums[0];
}
vector<pair<int, int>> dp(size);
dp[0] = pair<int, int>(0, nums[0]);
for (int i = 1; i <= size - 2; ++i)
{
dp[i].first = max(dp[i - 1].first, dp[i - 1].second);
dp[i].second = dp[i - 1].first + nums[i];
}
int maxRob = max(dp[size - 2].first, dp[size - 2].second);
dp[size - 1] = pair<int, int>(0, nums[size - 1]);
for (int i = size - 2; i >= 1; --i)
{
dp[i].first = max(dp[i + 1].first, dp[i + 1].second);
dp[i].second = dp[i + 1].first + nums[i];
}
maxRob = max(maxRob, max(dp[1].first, dp[1].second));
return maxRob;
}
LC337. 打家劫舍Ⅲ
pair<int, int> robLoop(TreeNode* root)
{
if (root == nullptr)
{
return {0, 0};
}
pair<int, int> left = robLoop(root->left);
pair<int, int> right = robLoop(root->right);
//pair<int, int> temp = {left.first + right.first, left.second + right.second};
pair<int, int> temp = {left.first + right.first,
max(left.second + right.second, max(left.first + right.second, left.second + right.first))};
return {max(temp.first, temp.second), temp.first + root->val};
}
int rob(TreeNode* root)
{
pair<int, int> result = robLoop(root);
return max(result.first, result.second);
}