一遍過。

當前房屋偷與不偷取決于 前一個房屋和前兩個房屋是否被偷了。所以這里就更感覺到，當前狀態和前面狀態會有一種依賴關系，那么這種依賴關系都是動規的遞推公式。

class Solution {
public:int rob(vector<int>& nums) {vector<vector<int>> dp(40001,vector<int>(2,0));for(int i=1;i<=nums.size();i++){int tmp=max(dp[i-1][0],dp[i-1][1]);dp[i][0]=max(tmp,dp[i][0]);dp[i][1]=max(dp[i-1][0]+nums[i-1],dp[i][1]);}return max(dp[nums.size()][0],dp[nums.size()][1]);}
};

?題解的遞推公示少了一個維度，

決定dp[i]的因素就是第i房間偷還是不偷。

如果偷第i房間，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考慮的，找出 下標i-2（包括i-2）以內的房屋，最多可以偷竊的金額為dp[i-2] 加上第i房間偷到的錢。

如果不偷第i房間，那么dp[i] = dp[i - 1]，即考 慮i-1房，（注意這里是考慮，并不是一定要偷i-1房，這是很多同學容易混淆的點）

然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 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());dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[nums.size() - 1];}
};

?

首尾元素大概知道要分為是否考慮末尾元素，考慮了末尾元素的情況對應選取第二個到最后一個元素，沒有題解方法清晰。看了題解。

?可以分為三種情況，

• 情況一：考慮不包含首尾元素；
• 情況二：考慮包含首元素，不包含尾元素；
• 情況二：考慮包含首元素，不包含尾元素；（其實情況二和情況三包括了情況一）

class 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]);return max(robrange(nums,0,nums.size()-2),robrange(nums,1,nums.size()-1));}int robrange(vector<int>& nums,int start,int end){if(start==end) return nums[end];vector<int> dp(nums.size()+1,0);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];}
};

?

?我一開始寫的遞歸版本，超出時間限制了。原因是在算左邊的孩子節點時，和算他的左右孩子節點會重復（各自會遞歸算一次）。

/*** 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:int rob(TreeNode* root) {int tmpl=0,tmpr=0 ;int tmpll=0,tmplr=0,tmprl=0,tmprr=0;if(root->left){tmpl=rob(root->left);if(root->left->left){tmpll=rob(root->left->left);}if(root->left->right){tmplr=rob(root->left->right);}}if(root->right){tmpr=rob(root->right);if(root->right->left){tmprl=rob(root->right->left);}if(root->right->right){tmprr=rob(root->right->right);}}return max(root->val+tmpll+tmplr+tmprl+tmprr,tmpl+tmpr);}
};

看了題解：對于樹的話，首先就要想到遍歷方式，前中后序（深度優先搜索）還是層序遍歷（廣度優先搜索）。本題一定是要后序遍歷，因為通過遞歸函數的返回值來做下一步計算。

要注意特判斷

if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return root->val;

?記憶化搜索：要會使用unordered_map

/*** 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> mp;int rob(TreeNode* root) {if(root==NULL) return 0;if(root->left==NULL&&root->right==NULL) return root->val;int tmpl=0,tmpr=0 ;int tmpll=0,tmplr=0,tmprl=0,tmprr=0;if(mp[root]) return mp[root];if(root->left){tmpl=rob(root->left);mp[root->left]=tmpl;if(root->left->left){tmpll=rob(root->left->left);mp[root->left->left]=tmpll;}if(root->left->right){tmplr=rob(root->left->right);mp[root->left->right]=tmplr;}}if(root->right){tmpr=rob(root->right);mp[root->right]=tmpr;if(root->right->left){tmprl=rob(root->right->left);mp[root->right->left]=tmprl;}if(root->right->right){tmprr=rob(root->right->right);mp[root->right->right]=tmprr;}}return max(root->val+tmpll+tmplr+tmprl+tmprr,tmpl+tmpr);}
};

動態規劃方法：

?對當前節點是偷與不偷兩種狀態：dp數組（dp table）以及下標的含義：下標為0記錄不偷該節點所得到的的最大金錢，下標為1記錄偷該節點所得到的的最大金錢。

如果是偷當前節點，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果對下標含義不理解就再回顧一下dp數組的含義）

如果不偷當前節點，那么左右孩子就可以偷，至于到底偷不偷一定是選一個最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

/*** 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:int rob(TreeNode* root) {vector<int> res=robrange(root);return max(res[0],res[1]);}vector<int> robrange(TreeNode* root){if(root==NULL) return vector<int>{0,0};vector<int> left=robrange(root->left);vector<int> right=robrange(root->right);return vector<int>{max(left[0],left[1])+max(right[0],right[1]),root->val+left[0]+right[0]};}
};

上題是樹形dp入門。