198.打家劫舍
dp数组含义：考虑前i个房间，偷到的最大钱数为dp[i]；
递推公式：
不偷第i个房间，则最大钱数为dp[i-1];
偷第i个房间，最大钱数为dp[i-2]+nums[i]；
取最大值，即为dp[i] = max(dp[i-1], dp[i-2]+nums[i])；
初始化：由于递推公式用到了i-1和i-2，所以初始化dp[0]和dp[1]，分别是nums[0]和max(nums[0],nums[1]);
遍历顺序：为了用到第0个和第1个元素，从前向后，从2开始遍历即可
class Solution { public: int rob(vector<int>& nums) { if(nums.size()==1) return nums[0]; if(nums.size()==2) return max(nums[0],nums[1]); 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
在打家劫舍的基础上加了限制条件-前后不能同时偷，所以分为两种情况，不考虑首元素，不考虑尾元素；
所以设计新的打家劫舍函数，输入数组，起始索引，终止索引，在首尾闭区间的范围（体现在初始化和for循环中）应用打家劫舍即可。
class Solution { public: int rob(vector<int>& nums) { if(nums.size()==1) return nums[0]; int result1 = ROB(nums, 0, nums.size()-2); int result2 = ROB(nums, 1, nums.size()-1); return max(result1,result2); } int ROB(vector<int>& nums, int start, int end){ if(start == end) 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]; } };337.打家劫舍III
本题为递归和动态规划的结合。
递归：返回当前节点偷或者不偷的最大价值，用一个长度为2的一维数组表示
递归三部曲：
1.返回类型和参数列表：返回一个长度2的一维数组，参数列表就传入树节点即可；
2.终止条件：当遍历到空节点时，偷或者不偷价值都是0，所以返回{0,0};
3.递归逻辑：先分别递归调用左孩子和右孩子的返回值，得到两个长度为2的数组，下面计算当前节点偷或不偷的最大钱数
当前节点偷：cur->val + left[0] + right[0] 解释：当前节点价值+左孩子都不偷的价值；
当前节点不偷：max(left[0],left[1])+max(right[0],right[1]) 解释：左右孩子各自的最大价值之和
动规五部曲：
1.dp数组含义：dp[0]和dp[1]分别代表当前节点不偷和偷对应的最大价值;
2.递推公式：和递归逻辑一致，首先调用左右子树得到左右子树各自偷或不偷的最大价值，从而推出当前节点偷或不偷的最大价值；
3.初始化：与终止条件一致，空节点对应起始，初始化为{0,0}；
4.遍历顺序：本题dp数组长度为2，直接显式写出，先0后1 或者 先1后0 都可以。
注：本题的二叉树遍历顺序是后序遍历（左右中）因为要知道左右子节点的返回结果才能递推到中间节点。
class Solution { public: int rob(TreeNode* root) { vector<int> result = ROB(root); return max(result[0],result[1]); } vector<int> ROB(TreeNode* cur){ if(cur==NULL) return {0,0}; vector<int> left=ROB(cur->left); vector<int> right=ROB(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}; } };
