LeetCode 第 198 題：打家劫舍
傳送門：198. 打家劫舍腋寨。
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋化焕。每間房內(nèi)都藏有一定的現(xiàn)金萄窜，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警查刻。
給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組键兜，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額穗泵。
示例 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 苇侵。
分析：狀態(tài)：dp[i] 考慮偷取 [0,i] 區(qū)間的房間號赶盔，能夠偷竊到的最高金額。對于每一個房屋榆浓，我們有偷和不偷兩種選擇于未，于是得到狀態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])。編碼的時候陡鹃，應(yīng)注意數(shù)組下標(biāo)越界問題烘浦。
Python 代碼：
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l == 0:
return 0
if l == 1:
return nums[0]
if l == 2:
return max(nums[0], nums[1])
dp = [0 for _ in range(l)]
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, l):
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
return dp[l - 1]
下面是一種節(jié)省空間復(fù)雜度的做法：
Python 代碼：
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
if n <= 2:
return max(nums)
dp = [-1] * 2
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i & 1] = max(nums[i] + dp[(i - 2) & 1], dp[(i - 1) & 1])
return dp[(n - 1) & 1]
再者，還可以使用“滾動數(shù)組”的寫法：
Python 代碼：“滾動數(shù)組”
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
if n <= 2:
return max(nums)
pre = nums[0]
cur = max(pre, nums[1])
for i in range(2, len(nums)):
temp = cur
cur = max(pre + nums[i], cur)
pre = temp
return cur
LeetCode 第 213 題：打家劫舍 II
傳送門：打家劫舍 II萍鲸。
你是一個專業(yè)的小偷闷叉，計劃偷竊沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金脊阴。這個地方所有的房屋都圍成一圈握侧，這意味著第一個房屋和最后一個房屋是緊挨著的。同時嘿期，相鄰的房屋裝有相互連通的防盜系統(tǒng)品擎，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警备徐。
給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組萄传，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額蜜猾。
示例 1:
輸入: [2,3,2] 輸出: 3 解釋: 你不能先偷竊 1 號房屋（金額 = 2）秀菱，然后偷竊 3 號房屋（金額 = 2）, 因為他們是相鄰的。示例 2:
輸入: [1,2,3,1] 輸出: 4 解釋: 你可以先偷竊 1 號房屋（金額 = 1）蹭睡，然后偷竊 3 號房屋（金額 = 3）衍菱。 偷竊到的最高金額 = 1 + 3 = 4 。
Python 代碼：節(jié)約空間復(fù)雜度的寫法
class Solution:
def __rob_helper(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
if n <= 2:
return max(nums)
dp = [-1] * 2
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i % 2] = max(nums[i] + dp[(i - 2) % 2], dp[(i - 1) % 2])
return dp[(n - 1) % 2]
def rob(self, nums):
"""
# 轉(zhuǎn)換成原問題去考慮
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l == 0:
return 0
if l <= 3:
return max(nums)
# 搶第一家到倒數(shù)第二家得到的金錢最大值
res1 = self.__rob_helper(nums[:-1])
# 搶第二家到最后一家得到的金錢最大值
res2 = self.__rob_helper(nums[1:])
return max(res1, res2)
Java 代碼：
LeetCode 第 337 題：打家劫舍 III
傳送門：337. 打家劫舍 III棠笑。
在上次打劫完一條街道之后和一圈房屋后梦碗，小偷又發(fā)現(xiàn)了一個新的可行竊的地區(qū)。這個地區(qū)只有一個入口，我們稱之為“根”洪规。 除了“根”之外印屁，每棟房子有且只有一個“父“房子與之相連。一番偵察之后斩例，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”雄人。 如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警念赶。
計算在不觸動警報的情況下础钠，小偷一晚能夠盜取的最高金額。
示例 1:
輸入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 輸出: 7 解釋: 小偷一晚能夠盜取的最高金額 = 3 + 3 + 1 = 7.示例 2:
輸入: [3,4,5,1,3,null,1] 3 / \ 4 5 / \ \ 1 3 1 輸出: 9 解釋: 小偷一晚能夠盜取的最高金額 = 4 + 5 = 9.
說明：二叉樹的問題叉谜，通常都用于考察遞歸旗吁。
分析：對于一個結(jié)點來說，分類討論：1停局、偷這個結(jié)點很钓；2、不偷這個結(jié)點董栽。本質(zhì)上與這個系列的第 1 個問題（即 第 198 題）是一樣的码倦。
注意這個結(jié)構(gòu)：
if (root.left != null) {
val += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
val += rob(root.right.left) + rob(root.right.right);
}
Java 代碼：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public int rob(TreeNode root) {
// 既然是遞歸求解，一定是先寫遞歸終止條件
if (root == null) {
return 0;
}
int val = root.val;
if (root.left != null) {
val += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
val += rob(root.right.left) + rob(root.right.right);
}
return Math.max(val, rob(root.left) + rob(root.right));
}
}
（本節(jié)完）
