House Robber
原题链接House Robber
给定一个数组，选取一些元素使得总和最大，选取规则为
- 不能连续取两个元素，即选取的元素之间至少要间隔一个其它元素
每个元素都有选与不选两种可能，使得用动态规划求解，令dp[n]表示nums[0 : n)的选取结果
代码如下
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> dp(nums.size() + , );
for(int i = ; i < dp.size(); ++i)
dp[i] = std::max(nums[i - ] + dp[i - ], dp[i - ]);
return dp[nums.size() + ];
}
};
观察发现实际上dp数组只用到了dp[i-2]和dp[i-1]，所以可以优化空间复杂度
class Solution {
public:
int rob(vector<int>& nums) {
int pprev = , prev = , cur = ;
for(int i = ; i < nums.size(); ++i)
{
cur = std::max(nums[i] + pprev, prev);
pprev = prev;
prev = cur;
}
return cur;
}
};
House Robber II
原题链接House Robber II
意思是给定的数组是循环的，第一个挨着最后一个。要求和上面一样
这种情况下就不能用上面的方法了，因为如果同时选择了第一个和最后一个，就不符合要求。所以需要单独分开计算，分两种情况（n是给定数组元素个数）
- 选择第一个，此时最后的结果相当于nums[0] + max_sum(nums[2 : n - 2])
- 不选择第一个，此时最后的结果为max_sum(nums[1 : n - 1])
代码如下
class Solution {
public:
int rob(vector<int>& nums) {
return (nums.empty())
?
: std::max(nums[] + max_sum(nums, , nums.size() - ), max_sum(nums, , nums.size()));
}
private:
int max_sum(vector<int>& nums, int first, int last)
{
int pprev = , prev = , cur = ;
for(int i = first; i < last; ++i)
{
cur = std::max(nums[i] + pprev, prev);
pprev = prev;
prev = cur;
}
return cur;
}
};
House Robber III
原题链接House Robber III
要求和上面一样，但这回是二叉树，相连的父子节点不能同时选择
遍历一遍二叉树即可（不考虑重复情况下，复杂度较高）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
return max_sum(root, false);
}
private:
int max_sum(TreeNode* root, bool robbed)
{
if(!root) return ;
if(robbed)
return max_sum(root->left, false) + max_sum(root->right, false);
else
return std::max(root->val + max_sum(root->left, true) + max_sum(root->right, true),
max_sum(root->left, false) + max_sum(root->right, false));
}
};
由于在max_sum函数的else语句块中需要重复遍历两次root->left和root->right，会造成复杂度很高，解决办法是记录下已经计算过的节点
遍历一遍二叉树，通过unordered_map记录已计算过的节点（考虑重复情况，复杂度较低）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
return max_sum(root, false);
}
private:
int max_sum(TreeNode* root, bool robbed)
{
if(!root) return ;
if(robbed)
return max_sum(root->left, false) + max_sum(root->right, false);
else
return map_.find(root) != map_.end()
? map_[root]
: map_[root] = std::max(root->val + max_sum(root->left, true) + max_sum(root->right, true),
max_sum(root->left, false) + max_sum(root->right, false));
}
private:
unordered_map<TreeNode*, int> map_;
};