---

198.打家劫舍

題目鏈接

思路

1. 確定dp數組（dp table）以及下標的含義
   dp[i]：考慮下標i以內的房屋，最多可以偷竊的金額為dp[i]。
   注意：dp[i]不是一定要偷第i個房間，它代表的是從0-i的范圍房間內能偷的最大值。
2. 確定遞推公式
   決定dp[i]的條件有第i房間偷還是不偷。
   如果偷第i房間，那么dp[i] = dp[i - 2] + nums[i]
   如果不偷第i房間，那么dp[i] = dp[i - 1]，即考慮 i-1房
   然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
3. dp數組如何初始化
   從遞推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])可以看出，遞推公式的基礎就是dp[0] 和 dp[1]。從dp[i]的定義上來講，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);
   vector dp(nums.size());
   dp[0] = nums[0];
   dp[1] = max(nums[0], nums[1]);
4. 確定遍歷順序
   dp[i] 是根據dp[i - 2] 和 dp[i - 1] 推導出來的，那么一定是從前到后遍歷
5. 舉例推導dp數組

代碼實現

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()+1,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

題目鏈接

思路

這道題和上一道題幾乎是一模一樣，只不過是圍成一個圈，那么這道題最重要的點就是，怎么避免偷的房間首尾相連。
所以重點就是不讓他們首尾相連，那么可以分情況討論：

1. 不考慮首尾
2. 考慮首不考慮尾
3. 不考慮首考慮尾

而第一種情況包含在2和3情況里，直接討論2和3情況即可，這樣一個環形數組又變成了線型數組，和打家劫舍一模一樣。

代碼實現

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

---

337.打家劫舍 III

題目鏈接

思路

這道題比上面那道題又加了一個檔次，是二叉樹和動態規劃的結合運用，第一次見我也是一臉懵逼。這道題用遞歸結構分析：

1. 確定遞歸函數的參數和返回值
   這里我們要求一個節點偷與不偷的兩個狀態所得到的金錢，那么返回值就是一個長度為2的數組。dp數組以及下標的含義：下標為0記錄不偷該節點所得到的的最大金錢，下標為1記錄偷該節點所得到的的最大金錢。
2. 確定終止條件
   在遍歷的過程中，如果遇到空節點的話，很明顯，無論偷還是不偷都是0，所以就返回{0,0}。這也相當于dp數組的初始化
3. 確定遍歷順序
   首先明確的是使用后序遍歷。 因為要通過遞歸函數的返回值來做下一步計算。
4. 確定單層遞歸的邏輯
   如果是偷當前節點，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0];
   如果不偷當前節點，那么左右孩子就可以偷，至于到底偷不偷一定是選一個最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
   最后當前節點的狀態就是{val2, val1}；

代碼實現

class Solution {
public:vector<int> robTree(TreeNode* root){if(root==nullptr)return {0,0};//dp[0]為當前未偷，dp[1]為當前偷了vector<int> left=robTree(root->left);vector<int> right=robTree(root->right);int val1=max(left[1],left[0])+max(right[0],right[1]);int val2=root->val+left[0]+right[0];return {val1,val2};}int rob(TreeNode* root) {vector<int> result=robTree(root);return max(result[0],result[1]);}
};

記憶化遞歸法（其他解法）

可以使用一個map把計算過的結果保存一下，這樣如果計算過孫子了，那么計算孩子的時候可以復用孫子節點的結果。
代碼如下：

class Solution {
public:unordered_map<TreeNode* , int> umap; // 記錄計算過的結果int rob(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return root->val;if (umap[root]) return umap[root]; // 如果umap里已經有記錄則直接返回// 偷父節點int val1 = root->val;if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳過root->leftif (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳過root->right// 不偷父節點int val2 = rob(root->left) + rob(root->right); // 考慮root的左右孩子umap[root] = max(val1, val2); // umap記錄一下結果return max(val1, val2);}
};

---