198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

198.打家劫舍 

class Solution {
public: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-1],dp[i-2]+nums[i]);return dp[nums.size()-1];}
};

 213.打家劫舍II  

class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==0)return 0;if(nums.size()==1)return nums[0];int res1=robRange(nums,0,nums.size()-2);int res2=robRange(nums,1,nums.size()-1);return max(res1,res2);}int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp(nums.size());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 - 2] + nums[i], dp[i - 1]);}return dp[end];}
};

337.打家劫舍III

/*** 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 {
public:unordered_map<TreeNode*,int>map;int rob(TreeNode* root) {if(root==NULL)return 0;if(root->left==NULL&&root->right==NULL)return root->val;if(map[root])return map[root];int val1=root->val;if(root->left)val1+=rob(root->left->right)+rob(root->left->left);if(root->right)val1+=rob(root->right->left)+rob(root->right->right);int val2=rob(root->left)+rob(root->right);map[root]=max(val1,val2);return max(val1,val2);}
};