本文主要是介绍leetcode笔记-House Robber，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.给定一个数组，相邻的两个数不能取，从头到尾能取到的和的最大值？
思路：动态规划
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
dp[0]=nums[0];dp[1]=max(nums[0],nums[1])
class Solution {//动态规划dp[i]=max(dp[i-1],dp[i-2]+nums[i])//dp[0]=nums[0];dp[1]=max(nums[0],nums[1])
public:int rob(vector<int>& nums) {vector<int> dp;if(nums.size()==0) return 0;if(nums.size()==1) return nums[0];if(nums.size()==2) return max(nums[0],nums[1]);dp={nums[0],max(nums[0],nums[1])};for(int i=2;i<nums.size();i++){dp.push_back(max(dp[i-1],dp[i-2]+nums[i]));}return dp.back();}
};2.头连着尾？
思路：动态规划（分两种情况，一个是从第二家开始到最后一家，另一个是从第一家开始到最后一家）
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
dp[0]=nums[0];dp[1]=max(nums[0],nums[1])
<span style="font-family:Times New Roman;">c<span style="font-size:18px;">lass Solution {
public:int rob(vector<int>& nums) {if(nums.size()==0) return 0;if(nums.size()==1) return nums[0];if(nums.size()==2) return max(nums[0],nums[1]);if(nums.size()==3) return max(nums[0],max(nums[1],nums[2]));vector<int> dp={nums[0], max(nums[0],nums[1])};//从第一个家到倒数第二家for(int i=2;i<nums.size()-1;i++){dp.push_back(max(dp[i-1],dp[i-2]+nums[i]));}vector<int> dp1={0,nums[1], max(nums[1],nums[2]),}; //从第二家到最后一家for(int i=3;i<nums.size();i++){dp1.push_back(max(dp1[i-1],dp1[i-2]+nums[i]));}return max(dp.back(),dp1.back());}
};</span></span>3.给定一个树，相邻的节点不能取，能取到的和的最大值？
思路1：深度优先遍历二叉树，每次遍历返回两个值：分别表示偷窃或者不偷窃当前节点可以获得的最大收益。cur and pre
后序遍历
/**
* 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) {
if(root==NULL)
return 0;
dfs(root);
return max(dp1[root],dp2[root]);
}
void dfs(TreeNode* node){
if(node==NULL)
return;
dfs(node->left);
dfs(node->right);//实际干活的代码写在这两个递归之后，
//表示先处理一个节点的左右子树之后，才考虑本身节点（后序遍历处理手法）
dp1[node]=dp2[node->left]+dp2[node->right]+node->val;
//dp2[NULL]是等于0的，当前节点被盗时，其左右子节点都不能被盗
dp2[node]=max(max(dp1[node->left]+dp1[node->right],dp2[node->left]+dp2[node->right]),max(dp1[node->left]+dp2[node->right],dp1[node->right]+dp2[node->left]));//当前节点不被盗时，取其左右节点都被盗、左右节点都不被盗、左节点被盗有节点不被盗、左节点被盗右节点不被盗中最大的一个值
}
private:
map<TreeNode*,int> dp1; //当前节点被盗，
map<TreeNode*,int> dp2;//当前节点不被盗
};这篇关于leetcode笔记-House Robber的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
