代碼隨想錄算法訓練營第五十天

198.打家劫舍

題目鏈接：198.打家劫舍

1. 確定dp數組以及下標的含義：dp[i]：考慮下標i（包括i）以內的房屋，最多可以偷竊的金額為dp[i]。
2. 確定遞推公式：max(dp[i - 1], dp[i - 2] + nums[i]);，不偷當前節點和偷當前節點哪個獲利最大就取哪個
3. dp數組如何初始化：dp[0]=nums[0]，只有一個必須偷。dp[1]=max(nums[0],nums[1])一共2個元素，只能偷一個最大的
4. 確定遍歷順序：從前向后遍歷。
5. 打印dp數組。

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 1)return nums[0];vector<int> dp(nums.size(), 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

題目鏈接：213.打家劫舍II
偷第一家就不能偷最后一家，偷最后一家就不能偷第一家，分別將兩種狀態求出，再從二者之間找最大值。兩種情況分別可以用上題方法求解。

class Solution {
public:int Rob(vector<int>& nums,int start, int end){if(start==end)return nums[start];vector<int> dp(nums.size(), 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 - 1], dp[i - 2] + nums[i]);}return dp[end];}int rob(vector<int>& nums) {if(nums.size()==1)return nums[0];int first = Rob(nums,0,nums.size()-2);int last = Rob(nums, 1, nums.size()-1);return max(first,last);}
};

---

337.打家劫舍III

題目鏈接：337.打家劫舍III
dp數組表示，每個節點偷當前節點和不偷當前節點可以取得的最大價值。要求當前節點值需要知道左右節點的值，所以是后序遍歷。最后再偷根節點和不偷根節點之間取一個最大值即可。

/*** 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:vector<int> Rob(TreeNode* cur){if(cur==nullptr)return {0,0};vector<int> left = Rob(cur->left);vector<int> right = Rob(cur->right);vector<int>dp(2);//定義一個dp數組dp[0]表示當前節點不偷可以獲得的最大金幣,dp[1]表示偷當前節點可以獲得的最大金幣dp[0] = max(left[0],left[1])+max(right[0],right[1]);//不偷當前節點，那它的子節點可以選擇偷或者不偷，左子偷不偷選最大的+右子偷不偷選最大的dp[1] = left[0]+right[0]+cur->val;//偷當前節點，左右子都不能偷，所以等于左不偷+右不偷+當前節點的值return dp;}int rob(TreeNode* root) {return max(Rob(root)[0],Rob(root)[1]);}
};

---