198. 打家劫舍
- 思路
- example
- 二維DP
- dp[i][j]: 房屋0,...,i; 并且第i個房屋狀態(tài)為j 的最高金額
- j = 0: 不搶父能； j = 1: 搶 (帶狀態(tài)）
- 狀態(tài)是i的單個狀態(tài)，不是0--i的整體狀態(tài)
- 遞推公式：
有可能連續(xù)幾個房屋不搶
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) 取決于前一天的情況
dp[i][1] = dp[i-1][0] + nums[i]
- 復(fù)雜度. 時間：O(n), 空間: O(n)
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [[0] * 2 for _ in range(n)]
dp[0][0] = 0
dp[0][1] = nums[0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1])
dp[i][1] = dp[i-1][0] + nums[i]
return max(dp[n-1])
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [[0 for _ in range(2)] for _ in range(n)]
dp[0][0] = 0
dp[0][1] = nums[0]
for i in range(1, n):
dp[i][0] = max(dp[i-1])
dp[i][1] = dp[i-1][0] + nums[i]
return max(dp[n-1])
-
一維DP, 不帶狀態(tài)
- dp[i]: 房屋0,...,i; 最高金額
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
第i個不搶 vs 搶 (第i-1個必然不搶, 所以由兩天前的狀態(tài)轉(zhuǎn)移而來)
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp = [0 for _ in range(n)]
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
return dp[n-1]
- 可以空間優(yōu)化
213. 打家劫舍 II
- 思路
- example
- 房屋圍成一圈, 轉(zhuǎn)化為兩個問題I
- 第0個不搶，最后一個可能搶也可能不搶口猜。轉(zhuǎn)化為問題1,...,n-1
- 第0個搶冻押，最后一個必然不搶填硕。轉(zhuǎn)化為問題0,...,n-2
注意指標(biāo)映射關(guān)系以及corner case （1個2個元素的情況)
- 復(fù)雜度. 時間：O(n), 空間: O(n)
class Solution:
def rob(self, nums: List[int]) -> int:
def rob_range(nums, start, end):
n = end - start + 1
if n == 1:
return nums[start]
dp = [0 for _ in range(n)]
dp[0] = nums[start]
dp[1] = max(nums[start], nums[start+1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + nums[start+i])
return dp[n-1]
n = len(nums)
if n == 1:
return nums[0]
return max(rob_range(nums, 0, n-2), rob_range(nums, 1, n-1))
class Solution:
def rob(self, nums: List[int]) -> int:
def rob_range(start, end):
n = end - start + 1
if n == 1:
return nums[start]
dp = [0 for _ in range(n)]
dp[0] = nums[start]
dp[1] = max(nums[start], nums[start+1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2]+nums[start+i])
return dp[n-1]
n = len(nums)
if n == 1:
return nums[0]
return max(rob_range(1, n-1), rob_range(0, n-2))
337. 打家劫舍 III
- 思路
- example
- 遞歸滔驾，后序遍歷错森，自下而上
-
樹形DP （在樹的結(jié)構(gòu)上使用DP）
- 返回值包括 當(dāng)前根節(jié)點(diǎn)的兩種狀態(tài)
- 復(fù)雜度. 時間：O(?), 空間: O(?)
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def traversal(root):
if root == None:
return 0, 0
left0, left1 = traversal(root.left)
right0, right1 = traversal(root.right)
return max(left0, left1)+max(right0, right1), left0+right0+root.val
return max(traversal(root))
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def traversal(root):
if root == None:
return 0, 0
left0, left1 = traversal(root.left)
right0, right1 = traversal(root.right)
return max(left0, left1)+max(right0, right1), left0+right0+root.val
return max(traversal(root))
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def traverse(root):
if root == None:
return 0, 0
left_0, left_1 = traverse(root.left)
right_0, right_1 = traverse(root.right)
return max(left_0, left_1)+max(right_0, right_1), left_0 + right_0 + root.val
return max(traverse(root))
