打家劫舍

力扣題目鏈接(opens new window)

你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動(dòng)報(bào)警。

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你 不觸動(dòng)警報(bào)裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。

• 示例 1：
• 輸入：[1,2,3,1]
• 輸出：4

解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。 偷竊到的最高金額 = 1 + 3 = 4 。

• 示例 2：
• 輸入：[2,7,9,3,1]
• 輸出：12 解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。 偷竊到的最高金額 = 2 + 9 + 1 = 12 。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

思路

由題意，我們必須隔一家偷一家，因此，偷不偷當(dāng)前這家取決于上一家有沒有被偷

這有很明顯的dp傾向

五步走

1、確定dp數(shù)組含義

dp[i]:偷房屋i最多能得到的錢是dp[i]

2、確定遞推公式

根據(jù)dp含義，遍歷到當(dāng)前位置時(shí)，我們可以得到兩種情況：偷房屋i和不偷房屋i

（1）偷

如果偷當(dāng)前的房屋i的話，那么當(dāng)前偷盜總金額dp[i] = dp[i - 2] + nums[i]， 即偷了這一家和上上家

（2）不偷

如果選擇不偷當(dāng)前的房屋i的話，那么房屋i的上一家（即房屋i - 1）就是可以偷的了，因此dp[i] = dp[i - 1]

注意，這里如果不偷當(dāng)前的房屋i，不是意味著必須偷上一家的

偷不偷某一家只取決于能不能最后得到最大的盜竊金額

綜上，本題的遞推公式應(yīng)該是dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);

3、初始化

由上述公式可知，遞推的起點(diǎn)應(yīng)該是dp[0]和dp[1]，所以要初始化這兩玩意

結(jié)合題意想一下這兩個(gè)情況出現(xiàn)場景

如果小偷在第一家的時(shí)候就決定偷，那就會有dp[0]，而此時(shí)dp[0]一定是nums[0]

如果小偷決定先不偷第一家，看看第二家先，那此時(shí)就會有dp[1]

而根據(jù)遞推公式的含義，小偷仍然可以選擇偷或不偷第二家

如果不偷，那當(dāng)前的盜竊金額就維持遍歷到第一家時(shí)的水平，即nums[0]

不是不偷第一家才到的第二家嗎，怎么現(xiàn)在第二家不偷第一家反而有值了呢？

因?yàn)槿绻谝患也煌?，看第二家還不偷的話就，最后的結(jié)果肯定不是最大的，因此如果不偷第二家就默認(rèn)你偷了第一家

如果選擇偷，那就更新盜竊金額為nums[1]

上述兩種情況，選擇金額最大的情況作為dp[1]，即dp[1] = max(nums[0], nums[1]);

4、遍歷順序

因?yàn)閐p[i]由dp[i - 2]和dp[i - 1]推導(dǎo)得到，所以要從前向后遍歷

代碼

class Solution {
public:
    int rob(vector<int>& nums) {
        //處理異常：當(dāng)數(shù)組只有一個(gè)數(shù)或0個(gè)數(shù)
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        //創(chuàng)建dp數(shù)組
        vector<int> dp(nums.size(), 0);
        //初始化
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        //遍歷dp數(shù)組
        for(int i = 2; i < nums.size(); ++i){
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.size() - 1];
    }
};

打家劫舍II（環(huán)結(jié)構(gòu)）

力扣題目鏈接(opens new window)

你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金。這個(gè)地方所有的房屋都 圍成一圈 ，這意味著第一個(gè)房屋和最后一個(gè)房屋是緊挨著的。同時(shí)，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動(dòng)報(bào)警 。

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你 在不觸動(dòng)警報(bào)裝置的情況下 ，能夠偷竊到的最高金額。

示例 1：

輸入：nums = [2,3,2] 輸出：3 解釋：你不能先偷竊 1 號房屋（金額 = 2），然后偷竊 3 號房屋（金額 = 2）, 因?yàn)樗麄兪窍噜彽摹?/p>

示例 2： 輸入：nums = [1,2,3,1] 輸出：4 解釋：你可以先偷竊 1 號房屋（金額 = 1），然后偷竊 3 號房屋（金額 = 3）。偷竊到的最高金額 = 1 + 3 = 4 。

示例 3： 輸入：nums = [0] 輸出：0

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

思路

這里題目將數(shù)組改成"環(huán)"結(jié)構(gòu)了，因此會多出以下情況：

（1）情況1：不偷首尾

nums[i]:[1, 6, 1, 9, 1]
            -------

因?yàn)橄噜彽牟蛔屚?，在環(huán)中，首尾也是相鄰的，因此也不能偷

（2）情況2：不偷第一家

nums[i]:[1, 6, 1, 9, 1]
            ----------

不偷第一家就可以規(guī)避環(huán)結(jié)構(gòu)帶來的相鄰問題

（3）情況3：不偷最后一家

nums[i]:[1, 6, 1, 9, 1]
         ----------

同理，不偷最后一家也行

綜上所述，實(shí)際上情況2、3已經(jīng)解決了情況1的問題（即包含了情況1），所以只需考慮后兩個(gè)即可

其余部分與第一題一致（核心遞推部分一致）

代碼

class Solution {
private://與上題一致的處理，這里的遍歷區(qū)間需要自行給出
    int robDeal(vector<int>& nums, int start, int end){
        //處理異常：遍歷區(qū)間相等，說明只有一個(gè)元素，返回該元素
        if(start == end) return nums[start];

        //定義dp數(shù)組
        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]);//注意嚴(yán)格按照dp數(shù)組含義來寫
        }
        return dp[end];
    }
public:
    int rob(vector<int>& nums) {
        //異常處理
        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return nums[0];

        //調(diào)用搶劫函數(shù)，計(jì)算情況2、3下的盜竊金額，選大的作為結(jié)果
        int robRes2 = robDeal(nums, 1, nums.size() - 1);//情況2：不偷第一家
        int robRes3 = robDeal(nums, 0, nums.size() - 2);//情況3：不偷第最后一家

        return max(robRes2, robRes3);
    }
};

打家劫舍III（樹形DP）

力扣題目鏈接(opens new window)

在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為“根”。 除了“根”之外，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警。

計(jì)算在不觸動(dòng)警報(bào)的情況下，小偷一晚能夠盜取的最高金額。

思路

本題為樹形DP，本質(zhì)上是在遍歷樹結(jié)構(gòu)的過程中計(jì)算狀態(tài)轉(zhuǎn)移，因此解題過程是遵循二叉樹的解題步驟

這里的狀態(tài)是什么？其實(shí)就是節(jié)點(diǎn)上的狀態(tài)，即偷當(dāng)前節(jié)點(diǎn)，或者不偷當(dāng)前節(jié)點(diǎn)

每個(gè)節(jié)點(diǎn)都有一個(gè)長度為2的數(shù)組來保存偷或不偷后續(xù)節(jié)點(diǎn)所得到的最大金錢

三步走

1、確定遞歸函數(shù)的返回值與參數(shù)

因?yàn)橐蟪鲆粋€(gè)節(jié)點(diǎn)在 偷 與 不偷 兩個(gè)狀態(tài)下得到的金錢，所以要返回一個(gè)長度為2的數(shù)組

class Solution {
private:
    vector<int> robTree(TreeNode* cur){
        
    }
public:
    int rob(TreeNode* root) {

    }
};

這個(gè)數(shù)組就是dp數(shù)組

其含義是：[不偷之后節(jié)點(diǎn)所得到的最大金錢數(shù)， 偷之后節(jié)點(diǎn)所得到的最大金錢數(shù)]

2、確定終止條件

與常規(guī)遍歷二叉樹類似，我們遇到空節(jié)點(diǎn)就返回（注意是空節(jié)點(diǎn)而不是葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)本身有值）

怎么返回？當(dāng)然是返回[0, 0]，空節(jié)點(diǎn)偷不偷都沒有值

class Solution {
private:
    vector<int> robTree(TreeNode* cur){//確定遞歸函數(shù)返回值和參數(shù)
        //確定終止條件
        if(cur == NULL) return vector<int, int>{0, 0};
        
    }
public:
    int rob(TreeNode* root) {

    }
};

這相當(dāng)于dp數(shù)組的初始化

因?yàn)闃漤敳康臓顟B(tài)是由下面的子樹傳遞上來的，因此當(dāng)遍歷到葉子節(jié)點(diǎn)之后的空節(jié)點(diǎn)，說明到二叉樹的底部了，此時(shí)就是dp[0,0]

題外話：花括號初始化

在c++中進(jìn)行初始化，{}和()有什么區(qū)別？

{}通常被稱為花括號初始化，可以用于各種類型的初始化，包括基本類型和自定義類型，例如：

• 初始化int類型：int x{0};
• 初始化自定義類型：std::vector vec{1, 2, 3};

而()則是用于調(diào)用函數(shù)或構(gòu)造函數(shù)的括號，例如：

• 調(diào)用函數(shù)：foo(1, "hello");
• 構(gòu)造函數(shù)：std::pair<int, std::string> p(1, "hello");

對于vector{0, 0}的情況，{}被視為列表初始化vector，構(gòu)造一個(gè)包含0和0兩個(gè)元素的vector對象。而如果使用()，則會被視為調(diào)用vector的構(gòu)造函數(shù)，需要指定vector的大小和默認(rèn)值，例如：

• std::vector vec(2, 0);

這將創(chuàng)建一個(gè)包含2個(gè)元素且每個(gè)元素的值都為0的vector對象。

3、確定遍歷順序

因?yàn)楸緦庸?jié)點(diǎn)狀態(tài)需要靠其后的子節(jié)點(diǎn)的狀態(tài)來確定，相當(dāng)于要先遍歷左右節(jié)點(diǎn)再遍歷中間節(jié)點(diǎn)

該順序即后序遍歷

通過遞歸左節(jié)點(diǎn)，得到左節(jié)點(diǎn)偷與不偷的金錢。

通過遞歸右節(jié)點(diǎn)，得到右節(jié)點(diǎn)偷與不偷的金錢。

class Solution {
private:
    vector<int> robTree(TreeNode* cur){//確定遞歸函數(shù)返回值和參數(shù)
        //確定終止條件
        if(cur == NULL) return vector<int, int>{0, 0};
        
        //調(diào)用遞歸函數(shù)
        vector<int> left = robTree(cur->left);//左
        vector<int> right = robTree(cur->right);//右  
    }
public:
    int rob(TreeNode* root) {

    }
};

4、處理單層遞歸邏輯

通過遞歸，我們得到了當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)的偷與不偷的最大金錢情況

于是要開始計(jì)算當(dāng)前節(jié)點(diǎn)的兩個(gè)狀態(tài)

(1)偷當(dāng)前節(jié)點(diǎn)

如果選擇偷當(dāng)前節(jié)點(diǎn)，那么其左右子節(jié)點(diǎn)就不能再偷了，這件事怎么表示呢？就是選擇左右子節(jié)點(diǎn)的數(shù)組中，不偷后續(xù)節(jié)點(diǎn)所得到的數(shù)組值

即：val1 = cur->val + left[0] + right[0]; （當(dāng)前節(jié)點(diǎn)的值+左子節(jié)點(diǎn)的不偷值+右子節(jié)點(diǎn)的不偷值）

(2)不偷當(dāng)前節(jié)點(diǎn)

如果不偷當(dāng)前節(jié)點(diǎn)，那就可以去偷其左右子節(jié)點(diǎn)

注意，這里的偷是指可以選擇偷而不是必須偷，如果不偷總金額更大，那就不偷

即：val2 = max(left[0], left[1]) + max(right[0], right[1]);

計(jì)算完畢上述狀態(tài)后，當(dāng)前節(jié)點(diǎn)的數(shù)組中就記錄了[val1, val2]，分別是：偷當(dāng)前節(jié)點(diǎn)得到的最大金錢，不偷當(dāng)前節(jié)點(diǎn)得到的最大金錢

class Solution {
private:
    vector<int> robTree(TreeNode* cur){//確定遞歸函數(shù)返回值和參數(shù)
        //確定終止條件
        if(cur == NULL) return vector<int>{0, 0};
        
        //調(diào)用遞歸函數(shù)
        vector<int> left = robTree(cur->left);//左
        vector<int> right = robTree(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};
        
    }
public:
    int rob(TreeNode* root) {

    }
};

代碼

主函數(shù)中調(diào)用遞歸函數(shù)求根節(jié)點(diǎn)的dp數(shù)組，選值最大的情況返回即可

class Solution {
private:
    vector<int> robTree(TreeNode* cur){//確定遞歸函數(shù)返回值和參數(shù)
        //確定終止條件
        // if(cur == NULL) return vector<int, int>{0, 0};
        if(cur == NULL) return vector<int>{0, 0};
        
        //調(diào)用遞歸函數(shù)
        vector<int> left = robTree(cur->left);//左
        vector<int> right = robTree(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};
        
    }
public:
    int rob(TreeNode* root) {
        vector<int> res = robTree(root);
        return max(res[0], res[1]);
    }
};

坑：關(guān)于遞歸函數(shù)返回值順序

為什么在robTree返回時(shí)需要以{不偷，偷}（即{val2, val1}）的順序返回，而{val1, val2}則會導(dǎo)致結(jié)果錯(cuò)誤？

順一下，在處理單層邏輯時(shí)，我們是不是需要計(jì)算兩個(gè)值，一個(gè)是偷當(dāng)前節(jié)點(diǎn)的最優(yōu)解，另一個(gè)是不偷當(dāng)前節(jié)點(diǎn)的最優(yōu)解

假設(shè)當(dāng)前節(jié)點(diǎn)是A，其左右子節(jié)點(diǎn)分別為BC

如果我們令遞歸函數(shù)的返回值順序?yàn)閧不偷，偷}，即先返回不偷當(dāng)前節(jié)點(diǎn)的最優(yōu)解

那么，在使用BC的dp值計(jì)算A的dp值時(shí)，就可以直接使用BC的"不偷最優(yōu)解"進(jìn)行計(jì)算，從而馬上得到節(jié)點(diǎn)A的"不偷最優(yōu)解"

相反，如果此時(shí)先返回的是偷當(dāng)前節(jié)點(diǎn)的最優(yōu)解，由于不能同時(shí)偷相鄰的節(jié)點(diǎn)，還需要使用子節(jié)點(diǎn)不偷的最優(yōu)解來計(jì)算當(dāng)前的"偷最優(yōu)解"

即在先返回"偷最優(yōu)解"的情況下，如果要使用左右子節(jié)點(diǎn)BC的dp值來計(jì)算節(jié)點(diǎn)A的dp值的話，還要先用BC的子節(jié)點(diǎn)的"不偷最優(yōu)解"來計(jì)算BC的"偷最優(yōu)解"（因?yàn)槟愎嚼锩婢褪沁@么定義的），于是導(dǎo)致了一個(gè)死循環(huán)，就卡在這了，直到最后的子節(jié)點(diǎn)把"不偷最優(yōu)解"算完才會回到BC處計(jì)算A，然后之前暫存的節(jié)點(diǎn)dp數(shù)組值又會在下次計(jì)算中消失，導(dǎo)致全部亂掉。

這就有可能漏掉一些最優(yōu)解的情況（或者全錯(cuò)）

二刷

把之前偷和不偷的情況位置修改了一下，因?yàn)槲覀冃枰确祷夭煌担ㄔ蛏厦嬗姓f），所以就直接統(tǒng)一一下返回順序文章來源地址http://www.zghlxwxcb.cn/news/detail-420662.html

class Solution {
private:
    vector<int> robTree(TreeNode* node){
        if(node == nullptr) return vector<int> {0, 0};

        vector<int> left = robTree(node->left);
        vector<int> right = robTree(node->right);

        int val1 = max(left[1], left[0]) + max(right[0], right[1]);//不偷,看之前哪邊大取哪個(gè)
        int val2 = node->val + left[0] + right[0];//偷

        return {val1, val2};//{不偷，偷}
    }
public:
    int rob(TreeNode* root) {
        vector<int> res = robTree(root);
        return max(res[0], res[1]);
    }
};

到了這里，關(guān)于【LeetCode動(dòng)態(tài)規(guī)劃#11】打家劫舍系列題（涉及環(huán)結(jié)構(gòu)和樹形DP的討論）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！