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

● 198.���家劫舍

动规五部曲。

1、dp[j]含义。前j个房屋偷到的金额之和最大是dp[j]。

2、递推公式。递推公式要得出dp[i]，就是要确定第i个房屋是否打劫，那么也跟之前的背包问题一样，放与不放，对应的是两种结果，我们只需要取这两种结果的最大值就行，而不需要用if-else语句来判断放和不放两种情况。

第i个房屋不被打劫，肯定前一个房屋要被打劫，所以此时dp[i]=dp[i-1]。

第i个房屋被打劫，肯定前一个房屋不能被打劫，所以dp[i]=dp[i-2]+nums[i]。因为i-1个房屋不考虑。

因此dp[i]是这两个数的最大值：dp[i]=max(dp[i-1], dp[i-2]+nums[i])

3、初始化。初始化要根据dp[j]含义来，上面递推公式涉及到前两个房屋，所以下标为0和 为1的房屋都要初始化。前1个房屋偷到的金额之和是nums[0]，第2个房屋偷到的金额之和是max(nums[0],nums[1])。

或者说：只有1个房屋的话，就偷这一家，有2个房屋的话，偷其中金额大的那一家。

4、遍历顺序。到达第i个房屋，dp[i]需要根据前两个房屋的dp来，所以是正序遍历。

5、打印dp数组。

代码如下：

class Solution {public:    int rob(vector& nums) {        if(nums.size()==1)return nums[0];        vector dp(nums.size(),0);        dp[0]=nums[0];        dp[1]=max(nums[0],nums[1]);        for(int i=2;ileft);        vector dpRight=digui(root->right);                dp[0]=max(max(dpLeft[1]+dpRight[1],dpLeft[0]+dpRight[1]),max(dpLeft[1]+dpRight[0],dpLeft[0]+dpRight[0]));//没选自己，可能左右孩子全选，也可能不选        dp[1]=dpLeft[0]+dpRight[0]+root->val;//选自己，孩子肯定不选        return dp;    }     int rob(TreeNode* root) {        vector dp(2);        dp=digui(root);        return max(dp[0],dp[1]);    }};

打印dp数组。按照每个节点得到dp[0]、dp[1]的过程先推导一下。