198. 打家劫舍

思路：

動規五部曲：

1.dp數組及其下標的意義：dp數組表示當前房屋下偷與不偷的最大盜取金額

2.確定遞推公式：因為盜取房屋只能間隔盜取，并且還要取最大值。所以每個房屋都有盜取和不盜取兩個選擇，盜不盜取取決于金額，所以遞推公式為dp[ i ] = max（dp[ i-1] (不盜取），dp[i-2 ]+nums[ i ]（盜取））

3.dp數組的初始化：因為遞推公式要取最大盜取金額，同時金額都為非負數，所以初始化為最小值0

4.遍歷順序：從前往后

代碼：

class Solution {
public:int rob(vector<int>& nums) {vector<int> dp(nums.size(),0);if(nums.size() == 0)return 0;if(nums.size()==1)return nums[0];//一定不要忘了無法用遞推公式的情況//dp數組的初始化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];}
};

遇到的問題：

對于一開始如果nums的個數小于三，那么就無法應用遞推公式，需要手動判斷

213. 打家劫舍 II

思路：

此題與上一題不同的是，這次的家是環形的，而非線性。因為相鄰就不偷，所以第一個和最后一個只有一個可以偷，所以分兩種情況

1.dp數組及其下標的意義：

dp數組表示當前序號房屋下偷與不偷的最大盜取金額

2.確定遞推公式：

dp[ i ] = max（dp[ i-1] (不盜取），dp[i-2 ]+nums[ i ]（盜取））

3.dp數組的初始化：因為遞推公式要取最大盜取金額，同時金額都為非負數，所以初始化為最小值0

4.遍歷順序：從前往后

代碼：

class Solution {
public:int rob(vector<int>& nums) {if(nums.size() == 0)return 0;if(nums.size()==1)return nums[0];int result1 = caozuo(nums,1,nums.size()-1);int result2 = caozuo(nums,0,nums.size()-2);return max(result1,result2);}int caozuo(vector<int>& nums ,int start,int end){if(start == end)return nums[start];vector<int> dp(nums.size(),0);//此處相當于復制了一個dp數組，因為start和end是原來的dp數組截取的下標，所以長度不能動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];//此處因為最后的值為end}
};

遇到的問題：

對于在分情況討論只有頭房子和尾房子時，處理dp數組的方式與不分情況是一樣的

337. 打家劫舍 III

思路：

1.dp數組的意義：dp數組下標為0記錄不偷該節點所得到的的最大金錢，下標為1記錄偷該節點所得到的的最大金錢。

2.中止條件：cur ==NULL遇到葉子節點

3.遍歷順序：因為是二叉樹，所以遍歷順序從前中后遍歷中選擇，選擇后序遍歷，因為當前節點偷不偷取決于子節點

代碼：

class Solution{
public:int rob(TreeNode* root) {//dp數組采用一個動態數組,內部只有兩個元素，0和1，vector<int> result = caozuo(root);return max(result[0],result[1]);}vector<int> caozuo(TreeNode* cur){if(cur == NULL)return {0,0};//后序遍歷//左vector<int>left = caozuo(cur->left);//右vector<int>right = caozuo(cur->right);//中//偷父節點int val1 = cur->val + left[0]+right[0];//不偷父節點int val2 = max(left[0],left[1]) + max(right[0] ,right[1]);return {val2,val1};//{ }是列表的初始化來賦值數組}
};

遇到的問題：

1. return {val2,val1};//{ }是列表的初始化來賦值數組

2.為什么選擇從下往上偷，第一可以使用遞歸函數的返回值，第二符合動態規劃的思路（重疊子問題，最優子結構）