本文章代碼以c++為例！

一、力扣第198題：打家劫舍

題目：

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

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

示例 1：

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號(hào)房屋 (金額 = 1) ，然后偷竊 3 號(hào)房屋 (金額 = 3)。
?    偷竊到的最高金額 = 1 + 3 = 4 。

示例 2：

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

提示：

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

思路

大家如果剛接觸這樣的題目，會(huì)有點(diǎn)困惑，當(dāng)前的狀態(tài)我是偷還是不偷呢？

仔細(xì)一想，當(dāng)前房屋偷與不偷取決于 前一個(gè)房屋和前兩個(gè)房屋是否被偷了。

所以這里就更感覺到，當(dāng)前狀態(tài)和前面狀態(tài)會(huì)有一種依賴關(guān)系，那么這種依賴關(guān)系都是動(dòng)規(guī)的遞推公式。

當(dāng)然以上是大概思路，打家劫舍是dp解決的經(jīng)典問題，接下來我們來動(dòng)規(guī)五部曲分析如下：

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

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

1. 確定遞推公式

決定dp[i]的因素就是第i房間偷還是不偷。

如果偷第i房間，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考慮的，找出 下標(biāo)i-2（包括i-2）以內(nèi)的房屋，最多可以偷竊的金額為dp[i-2] 加上第i房間偷到的錢。

如果不偷第i房間，那么dp[i] = dp[i - 1]，即考 慮i-1房，（注意這里是考慮，并不是一定要偷i-1房，這是很多同學(xué)容易混淆的點(diǎn)）

然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

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

從遞推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，遞推公式的基礎(chǔ)就是dp[0] 和 dp[1]

從dp[i]的定義上來講，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

代碼如下：

vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

1. 確定遍歷順序

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

代碼如下：

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

1. 舉例推導(dǎo)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];
    }
};

• 時(shí)間復(fù)雜度: O(n)
• 空間復(fù)雜度: O(n)

# 總結(jié)

打家劫舍是DP解決的經(jīng)典題目，這道題也是打家劫舍入門級(jí)題目，后面我們還會(huì)變種方式來打劫的。

二、力扣第213題：打家劫舍 II

題目：

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

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

示例?1：

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

示例 2：

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

示例 3：

輸入：nums = [1,2,3]
輸出：3

提示：

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

思路

這道題目和198.打家劫舍

(opens new window)是差不多的，唯一區(qū)別就是成環(huán)了。

對(duì)于一個(gè)數(shù)組，成環(huán)的話主要有如下三種情況：

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

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

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

注意我這里用的是"考慮"，例如情況三，雖然是考慮包含尾元素，但不一定要選尾部元素！ 對(duì)于情況三，取nums[1] 和 nums[3]就是最大的。

而情況二 和 情況三 都包含了情況一了，所以只考慮情況二和情況三就可以了。

分析到這里，本題其實(shí)比較簡單了。 剩下的和198.打家劫舍

(opens new window)就是一樣的了。

代碼如下：

// 注意注釋中的情況二情況三，以及把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];
    }
};

• 時(shí)間復(fù)雜度: O(n)
• 空間復(fù)雜度: O(n)

# 總結(jié)

成環(huán)之后還是難了一些的， 不少題解沒有把“考慮房間”和“偷房間”說清楚。

這就導(dǎo)致大家會(huì)有這樣的困惑：情況三怎么就包含了情況一了呢？ 本文圖中最后一間房不能偷啊，偷了一定不是最優(yōu)結(jié)果。

所以我在本文重點(diǎn)強(qiáng)調(diào)了情況一二三是“考慮”的范圍，而具體房間偷與不偷交給遞推公式去抉擇。

這樣大家就不難理解情況二和情況三包含了情況一了。

三、力扣第337題：打家劫舍 III

題目：

小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為?root?。

除了?root?之外，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后，聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹”。 如果 兩個(gè)直接相連的房子在同一天晚上被打劫 ，房屋將自動(dòng)報(bào)警。

給定二叉樹的?root?。返回?在不觸動(dòng)警報(bào)的情況下?，小偷能夠盜取的最高金額?。

示例 1:

輸入: root = [3,2,3,null,3,null,1]
輸出: 7 
解釋:?小偷一晚能夠盜取的最高金額 3 + 3 + 1 = 7

示例 2:

輸入: root = [3,4,5,1,3,null,1]
輸出: 9
解釋:?小偷一晚能夠盜取的最高金額 4 + 5 = 9

提示：

• 樹的節(jié)點(diǎn)數(shù)在?[1, 104] 范圍內(nèi)
• 0 <= Node.val <= 104

思路

這道題目和 198.打家劫舍

(opens new window)，213.打家劫舍II

(opens new window)也是如出一轍，只不過這個(gè)換成了樹。

如果對(duì)樹的遍歷不夠熟悉的話，那本題就有難度了。

對(duì)于樹的話，首先就要想到遍歷方式，前中后序（深度優(yōu)先搜索）還是層序遍歷（廣度優(yōu)先搜索）。

本題一定是要后序遍歷，因?yàn)橥ㄟ^遞歸函數(shù)的返回值來做下一步計(jì)算。

與198.打家劫舍，213.打家劫舍II一樣，關(guān)鍵是要討論當(dāng)前節(jié)點(diǎn)搶還是不搶。

如果搶了當(dāng)前節(jié)點(diǎn)，兩個(gè)孩子就不能動(dòng)，如果沒搶當(dāng)前節(jié)點(diǎn)，就可以考慮搶左右孩子（注意這里說的是“考慮”）

# 暴力遞歸

代碼如下：

class Solution {
public:
    int rob(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) return root->val;
        // 偷父節(jié)點(diǎn)
        int val1 = root->val;
        if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳過root->left，相當(dāng)于不考慮左孩子了
        if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳過root->right，相當(dāng)于不考慮右孩子了
        // 不偷父節(jié)點(diǎn)
        int val2 = rob(root->left) + rob(root->right); // 考慮root的左右孩子
        return max(val1, val2);
    }
};

• 時(shí)間復(fù)雜度：O(n^2)，這個(gè)時(shí)間復(fù)雜度不太標(biāo)準(zhǔn)，也不容易準(zhǔn)確化，例如越往下的節(jié)點(diǎn)重復(fù)計(jì)算次數(shù)就越多
• 空間復(fù)雜度：O(log n)，算上遞推系統(tǒng)棧的空間

當(dāng)然以上代碼超時(shí)了，這個(gè)遞歸的過程中其實(shí)是有重復(fù)計(jì)算了。

我們計(jì)算了root的四個(gè)孫子（左右孩子的孩子）為頭結(jié)點(diǎn)的子樹的情況，又計(jì)算了root的左右孩子為頭結(jié)點(diǎn)的子樹的情況，計(jì)算左右孩子的時(shí)候其實(shí)又把孫子計(jì)算了一遍。

# 記憶化遞推

所以可以使用一個(gè)map把計(jì)算過的結(jié)果保存一下，這樣如果計(jì)算過孫子了，那么計(jì)算孩子的時(shí)候可以復(fù)用孫子節(jié)點(diǎn)的結(jié)果。

代碼如下：

class Solution {
public:
    unordered_map<TreeNode* , int> umap; // 記錄計(jì)算過的結(jié)果
    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里已經(jīng)有記錄則直接返回
        // 偷父節(jié)點(diǎn)
        int val1 = root->val;
        if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳過root->left
        if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳過root->right
        // 不偷父節(jié)點(diǎn)
        int val2 = rob(root->left) + rob(root->right); // 考慮root的左右孩子
        umap[root] = max(val1, val2); // umap記錄一下結(jié)果
        return max(val1, val2);
    }
};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(log n)，算上遞推系統(tǒng)棧的空間

# 動(dòng)態(tài)規(guī)劃

在上面兩種方法，其實(shí)對(duì)一個(gè)節(jié)點(diǎn) 偷與不偷得到的最大金錢都沒有做記錄，而是需要實(shí)時(shí)計(jì)算。

而動(dòng)態(tài)規(guī)劃其實(shí)就是使用狀態(tài)轉(zhuǎn)移容器來記錄狀態(tài)的變化，這里可以使用一個(gè)長度為2的數(shù)組，記錄當(dāng)前節(jié)點(diǎn)偷與不偷所得到的的最大金錢。

這道題目算是樹形dp的入門題目，因?yàn)槭窃跇渖线M(jìn)行狀態(tài)轉(zhuǎn)移，我們?cè)谥v解二叉樹的時(shí)候說過遞歸三部曲，那么下面我以遞歸三部曲為框架，其中融合動(dòng)規(guī)五部曲的內(nèi)容來進(jìn)行講解。

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

這里我們要求一個(gè)節(jié)點(diǎn) 偷與不偷的兩個(gè)狀態(tài)所得到的金錢，那么返回值就是一個(gè)長度為2的數(shù)組。

參數(shù)為當(dāng)前節(jié)點(diǎn)，代碼如下：

vector<int> robTree(TreeNode* cur) {

其實(shí)這里的返回?cái)?shù)組就是dp數(shù)組。

所以dp數(shù)組（dp table）以及下標(biāo)的含義：下標(biāo)為0記錄不偷該節(jié)點(diǎn)所得到的的最大金錢，下標(biāo)為1記錄偷該節(jié)點(diǎn)所得到的的最大金錢。

所以本題dp數(shù)組就是一個(gè)長度為2的數(shù)組！

那么有同學(xué)可能疑惑，長度為2的數(shù)組怎么標(biāo)記樹中每個(gè)節(jié)點(diǎn)的狀態(tài)呢？

別忘了在遞歸的過程中，系統(tǒng)棧會(huì)保存每一層遞歸的參數(shù)。

如果還不理解的話，就接著往下看，看到代碼就理解了哈。

1. 確定終止條件

在遍歷的過程中，如果遇到空節(jié)點(diǎn)的話，很明顯，無論偷還是不偷都是0，所以就返回

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

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

1. 確定遍歷順序

首先明確的是使用后序遍歷。 因?yàn)橐ㄟ^遞歸函數(shù)的返回值來做下一步計(jì)算。

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

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

代碼如下：

// 下標(biāo)0：不偷，下標(biāo)1：偷
vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右
// 中

1. 確定單層遞歸的邏輯

如果是偷當(dāng)前節(jié)點(diǎn)，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果對(duì)下標(biāo)含義不理解就再回顧一下dp數(shù)組的含義）

如果不偷當(dāng)前節(jié)點(diǎn)，那么左右孩子就可以偷，至于到底偷不偷一定是選一個(gè)最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

最后當(dāng)前節(jié)點(diǎn)的狀態(tài)就是{val2, val1}; 即：{不偷當(dāng)前節(jié)點(diǎn)得到的最大金錢，偷當(dāng)前節(jié)點(diǎn)得到的最大金錢}

代碼如下：

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

1. 舉例推導(dǎo)dp數(shù)組

以示例1為例，dp數(shù)組狀態(tài)如下：（注意用后序遍歷的方式推導(dǎo)）

最后頭結(jié)點(diǎn)就是 取下標(biāo)0 和 下標(biāo)1的最大值就是偷得的最大金錢。

遞歸三部曲與動(dòng)規(guī)五部曲分析完畢，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é)點(diǎn)。
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur，那么可以偷也可以不偷左右節(jié)點(diǎn)，則取較大的情況
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};

• 時(shí)間復(fù)雜度：O(n)，每個(gè)節(jié)點(diǎn)只遍歷了一次
• 空間復(fù)雜度：O(log n)，算上遞推系統(tǒng)棧的空間

# 總結(jié)

這道題是樹形DP的入門題目，通過這道題目大家應(yīng)該也了解了，所謂樹形DP就是在樹上進(jìn)行遞歸公式的推導(dǎo)。

所以樹形DP也沒有那么神秘！

只不過平時(shí)我們習(xí)慣了在一維數(shù)組或者二維數(shù)組上推導(dǎo)公式，一下子換成了樹，就需要對(duì)樹的遍歷方式足夠了解！

大家還記不記得我在講解貪心專題的時(shí)候，講到這道題目：貪心算法：我要監(jiān)控二叉樹！

(opens new window)，這也是貪心算法在樹上的應(yīng)用。那我也可以把這個(gè)算法起一個(gè)名字，叫做樹形貪心，哈哈哈

“樹形貪心”詞匯從此誕生文章來源地址http://www.zghlxwxcb.cn/news/detail-703492.html

到了這里，關(guān)于【LeetCode題目詳解】第九章 動(dòng)態(tài)規(guī)劃part09 198.打家劫舍 213.打家劫舍II 337.打家劫舍III（day48補(bǔ)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！