目錄

LeetCode:198.打家劫舍

基本思路

C++代碼

LeetCode:213.打家劫舍II

基本思路

C++代碼

LeetCode:337.打家劫舍III

基本思路

C++代碼

---

LeetCode:198.打家劫舍

力扣題目鏈接

文字講解：LeetCode:198.打家劫舍

視頻講解：動態(tài)規(guī)劃，偷不偷這個房間呢？

基本思路

????????看到這個問題，很容易想到，需要對當前房屋偷與不偷兩種狀態(tài)進行判斷，而這個狀態(tài)和前一個房間和前兩個房間是否被偷有很大的關(guān)系。

????????通過動規(guī)五部曲進行分析：

• 確定dp數(shù)組（dp table）以及下標的含義

????????dp[i]：考慮下標i（包括i）以內(nèi)的房屋，最多可以偷竊的金額為dp[i]。

• 確定遞推公式

????????首先決定dp[i]的因素就是第i房間偷還是不偷。而如果偷了第i個房間，那么其偷盜金額就和前兩個房間有關(guān)；如果不偷第i個房間，顯然dp[i]和前一個房間的金額相同。

????????因此容易推出遞推公式為：dp[i] = max(dp[i-1],dp[i-2]+nums[i]);

• dp數(shù)組如何初始化

? ? ? ? 因為題目明確說明街道上存在一個以上的房屋，當街道上只有一個房屋時，我們直接返回nums[0]，如果大于等于兩個房屋時，我們令dp[0]為nums[0],令dp[1] = max(nums[0],nums[1]);

• 確定遍歷順序

????????dp[i] 是根據(jù)dp[i - 2] 和 dp[i - 1] 推導出來的，那么一定是從前到后遍歷！

for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}

• 舉例推導dp數(shù)組

以示例二，輸入[2,7,9,3,1]為例,紅框dp[nums.size() - 1]為結(jié)果。

C++代碼

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];}
};

LeetCode:213.打家劫舍II

力扣題目鏈接

文字講解：LeetCode:213.打家劫舍II

視頻講解：動態(tài)規(guī)劃，房間連成環(huán)了那還偷不偷呢？

基本思路

? ? ? ? 這個題目相對于上一個題目，不同點在于街道上的房子練成了一個圈，那么我們到底應不應該選擇第一個房屋和最后一個房屋呢？

? ? ? ? 很容易想到可以分成三種情況：

• 情況一：考慮不包含首尾元素

• 情況二：考慮包含首元素，不包含尾元素

• 情況三：考慮包含尾元素，不包含首元素

????????而在情況二和情況三種我們提到可以考慮包含首尾元素，而不是一定包含，因此情況一的情形實際上是包含在情況二和情況三中的。

? ? ? ? 這個樣子我們和容易和上個題目中的動規(guī)五部曲進行相同的分析了。無非就是進行判斷的區(qū)間有所不同。

C++代碼

// 注意注釋中的情況二情況三，以及把198.打家劫舍的代碼抽離出來了
class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2); // 情況二int result2 = robRange(nums, 1, nums.size() - 1); // 情況三return max(result1, result2);}// 198.打家劫舍的邏輯int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp(nums.size());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];}
};

LeetCode:337.打家劫舍III

力扣題目鏈接

文字講解：LeetCode:337.打家劫舍III

視頻講解：動態(tài)規(guī)劃，房間連成樹了，偷不偷呢？

基本思路

????????這個題目結(jié)合了二叉樹的相關(guān)知識，如果忘記了的同學可以重新回顧一下二叉樹相關(guān)的知識和題目。這個題目當然也可以使用二叉樹遞歸的方法進行求解，但是我們知道二叉樹的時間復雜度遠大于動態(tài)規(guī)劃的時間復雜度，這就很容易導致出現(xiàn)超時的情況。

? ? ? ? 這道題目算是樹形dp的入門題目，因為是在樹上進行狀態(tài)轉(zhuǎn)移，我們在講解二叉樹的時候說過遞歸三部曲，那么下面我以遞歸三部曲為框架，其中融合動規(guī)五部曲的內(nèi)容來進行講解。

• 確定遞歸函數(shù)的參數(shù)和返回值

? ? ? ? 我們需要傳入的是根節(jié)點，而返回的是所能偷到的最大金額，因此返回值是int類型。對于每個二叉樹節(jié)點，我們需要求出對于當前節(jié)點偷與不偷兩個狀態(tài)。我們還需要設(shè)置一個函數(shù)，用來記錄每個節(jié)點偷與不偷狀態(tài)下所能獲得的最大金額。傳入的為當前節(jié)點的指針，返回為一個數(shù)組。

int rob(TreeNode* root)

vector<int> robTree(TreeNode* cur)

• 確定終止條件

????????對二叉樹的所有節(jié)點進行遍歷，當節(jié)點為空節(jié)點時，表示無論是否偷空節(jié)點，偷到的金額都為零，此時返回{0,0}。

if (cur == NULL) return vector<int>{0, 0};

• 確定遍歷順序

? ? ? ? 因為是否偷當前節(jié)點需要根據(jù)是否偷左右孩子獲得的最大金額決定。因此需要先遍歷左右孩子，在遍歷中間節(jié)點，即遍歷方式采用后序遍歷。

• 確定單層遞歸的邏輯

? ? ? ? 遍歷當前節(jié)點時，如果偷當前節(jié)點，那么就不能偷左右孩子，即取left[0]和right[0]；如果不偷當前節(jié)點，那么就對左右節(jié)點是否偷盜的可以獲得的金額求最大值。

vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右// 偷cur
int val1 = cur->val + left[0] + right[0];
// 不偷cur
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};

• 舉例推導dp數(shù)組

????????以示例1為例，dp數(shù)組狀態(tài)如下：

????????最后頭結(jié)點就是 取下標0 和 下標1的最大值就是偷得的最大金錢。

C++代碼

class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}// 長度為2的數(shù)組，0：不偷，1：偷vector<int> robTree(TreeNode* cur) {if (cur == NULL) return vector<int>{0, 0};vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);// 偷cur，那么就不能偷左右節(jié)點。int val1 = cur->val + left[0] + right[0];// 不偷cur，那么可以偷也可以不偷左右節(jié)點，則取較大的情況int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}
};