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 號房屋 (金額 = 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
思路
大家如果剛接觸這樣的題目，會(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ī)五部曲分析如下：
確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i]：考慮下標(biāo)i（包括i）以內(nèi)的房屋，最多可以偷竊的金額為dp[i]。
確定遞推公式
決定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]);
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]);
確定遍歷順序
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]);
舉例推導(dǎo)dp數(shù)組
以示例二，輸入[2,7,9,3,1]為例。
紅框dp[nums.size() - 1]為結(jié)果。
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 0: # 如果沒有房屋，返回0
return 0
if len(nums) == 1: # 如果只有一個(gè)房屋，返回其金額
return nums[0]
# 創(chuàng)建一個(gè)動(dòng)態(tài)規(guī)劃數(shù)組，用于存儲(chǔ)最大金額
dp = [0] * len(nums)
dp[0] = nums[0] # 將dp的第一個(gè)元素設(shè)置為第一個(gè)房屋的金額
dp[1] = max(nums[0], nums[1]) # 將dp的第二個(gè)元素設(shè)置為第一二個(gè)房屋中的金額較大者
# 遍歷剩余的房屋
for i in range(2, len(nums)):
# 對于每個(gè)房屋，選擇搶劫當(dāng)前房屋和搶劫前一個(gè)房屋的最大金額
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return dp[-1] # 返回最后一個(gè)房屋中可搶劫的最大金額
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 號房屋（金額 = 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
思路
這道題目和198.打家劫舍 是差不多的，唯一區(qū)別就是成環(huán)了。
對于一個(gè)數(shù)組，成環(huán)的話主要有如下三種情況：
情況一：考慮不包含首尾元素
情況二：考慮包含首元素，不包含尾元素請?zhí)砑訄D片描述
在這里插入圖片描述
情況三：考慮包含尾元素，不包含首元素
注意我這里用的是"考慮"，例如情況三，雖然是考慮包含尾元素，但不一定要選尾部元素！ 對于情況三，取nums[1] 和 nums[3]就是最大的。
而情況二 和 情況三 都包含了情況一了，所以只考慮情況二和情況三就可以了。
分析到這里，本題其實(shí)比較簡單了。 剩下的和198.打家劫舍 (opens new window)就是一樣的了。
總結(jié)
成環(huán)之后還是難了一些的， 不少題解沒有把“考慮房間”和“偷房間”說清楚。
這就導(dǎo)致大家會(huì)有這樣的困惑：情況三怎么就包含了情況一了呢？ 本文圖中最后一間房不能偷啊，偷了一定不是最優(yōu)結(jié)果。
所以我在本文重點(diǎn)強(qiáng)調(diào)了情況一二三是“考慮”的范圍，而具體房間偷與不偷交給遞推公式去抉擇。
這樣大家就不難理解情況二和情況三包含了情況一了。
class Solution:
def robrange(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
return dp[-1]
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
dp1 = self.robrange(nums[1:])
dp2 = self.robrange(nums[:len(nums)-1])
return max(dp1, dp2)
337.打家劫舍 III
在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為“根”。 除了“根”之外，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警。
計(jì)算在不觸動(dòng)警報(bào)的情況下，小偷一晚能夠盜取的最高金額。
思路
這道題目和 198.打家劫舍 ，213.打家劫舍II 也是如出一轍，只不過這個(gè)換成了樹。
如果對樹的遍歷不夠熟悉的話，那本題就有難度了。
對于樹的話，首先就要想到遍歷方式，前中后序（深度優(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)，就可以考慮搶左右孩子（注意這里說的是“考慮”）
暴力遞歸
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: TreeNode) -> int:
if root is None:
return 0
if root.left is None and root.right is None:
return root.val
# 偷父節(jié)點(diǎn)
val1 = root.val
if root.left:
val1 += self.rob(root.left.left) + self.rob(root.left.right)
if root.right:
val1 += self.rob(root.right.left) + self.rob(root.right.right)
# 不偷父節(jié)點(diǎn)
val2 = self.rob(root.left) + self.rob(root.right)
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ì)算了一遍。
動(dòng)態(tài)規(guī)劃
動(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)移，我們在講解二叉樹的時(shí)候說過遞歸三部曲，那么下面我以遞歸三部曲為框架，其中融合動(dòng)規(guī)五部曲的內(nèi)容來進(jìn)行講解。
確定遞歸函數(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ù)。
如果還不理解的話，就接著往下看，看到代碼就理解了哈。
確定終止條件
在遍歷的過程中，如果遇到空節(jié)點(diǎn)的話，很明顯，無論偷還是不偷都是0，所以就返回
if (cur == NULL) return vector<int>{0, 0};
這也相當(dāng)于dp數(shù)組的初始化
確定遍歷順序
首先明確的是使用后序遍歷。 因?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); // 右
// 中
確定單層遞歸的邏輯
如果是偷當(dāng)前節(jié)點(diǎn)，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果對下標(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};
舉例推導(dǎo)dp數(shù)組
以示例1為例，dp數(shù)組狀態(tài)如下：（注意用后序遍歷的方式推導(dǎo)）
最后頭結(jié)點(diǎn)就是 取下標(biāo)0 和 下標(biāo)1的最大值就是偷得的最大金錢。文章來源：http://www.zghlxwxcb.cn/news/detail-850835.html
遞歸三部曲與動(dòng)規(guī)五部曲分析完畢，C++代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-850835.html
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)棧的空間
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
# dp數(shù)組（dp table）以及下標(biāo)的含義：
# 1. 下標(biāo)為 0 記錄 **不偷該節(jié)點(diǎn)** 所得到的的最大金錢
# 2. 下標(biāo)為 1 記錄 **偷該節(jié)點(diǎn)** 所得到的的最大金錢
dp = self.traversal(root)
return max(dp)
# 要用后序遍歷, 因?yàn)橐ㄟ^遞歸函數(shù)的返回值來做下一步計(jì)算
def traversal(self, node):
# 遞歸終止條件，就是遇到了空節(jié)點(diǎn)，那肯定是不偷的
if not node:
return (0, 0)
left = self.traversal(node.left)
right = self.traversal(node.right)
# 不偷當(dāng)前節(jié)點(diǎn), 偷子節(jié)點(diǎn)
val_0 = max(left[0], left[1]) + max(right[0], right[1])
# 偷當(dāng)前節(jié)點(diǎn), 不偷子節(jié)點(diǎn)
val_1 = node.val + left[0] + right[0]
return (val_0, val_1)
到了這里，關(guān)于leetcode-打家劫舍專題系列(動(dòng)態(tài)規(guī)劃)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
