198. 打家劫舍
思路：
dp[i]：包含下标i时可以偷的最大金币数量为dp[i]，注意这里的i可以偷也可以不偷。递推关系：当i不投偷的时候，最大的金币数量就取决与dp[i-1]，当在i位置要偷的时候，最大的金币数量取决于dp[i-2]+nums[i]，因为相邻的房间不能偷，所以二者取最大值就是dp[i]。初始化：dp[0]=nums[0],dp[1]=max(nums[0]],nums[1])；遍历顺序：有递推关系知道遍历顺序是从小到大。
代码：
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(),0);
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 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-1],dp[i-2]+nums[i]);
}
return dp[end];
}
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);
}
};
337. 打家劫舍 III
思路：
这道题是树形dp问题，由递归的三步可以得到：1、确定递归函数的参数和返回值：对于每一个节点，都有偷与不偷两种状态，所以用一个有两个元素的一维数组来存储这些状态，用dp[0]表示不偷，用dp[1]表示偷。2、确立终止条件：如果遇到空节点，dp[0]=dp[1]=0，此时直接返回；3、确定单层遍历的逻辑：这里采用后序遍历，先遍历左节点和右节点，最后遍历中间节点，直到到达跟节点。对于每个节点而言，偷的话，dp[1]就由当前节点的值和左右节点不偷的情况组成；如果不偷的话，当前dp[0]就有其左右节点偷与不偷的最大值组成（即使当前节点不偷，其左右节点也可以不偷）。
代码：
/**
* 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:
vector<int> robtree(TreeNode* cur)
{
if(cur==NULL)return {0,0};
vector<int> left = robtree(cur->left);
vector<int> right = robtree(cur->right);
int val0=max(left[0],left[1])+max(right[0],right[1]);
int val1=cur->val+left[0]+right[0];
return {val0,val1};
}
int rob(TreeNode* root) {
vector<int> dp=robtree(root);
return max(dp[0],dp[1]);
}
};
