198. 打家劫舍
- 思路
- example
- 二维DP
- dp[i][j]: 房屋0,...,i; 并且第i个房屋状态为j 的最高金额
- j = 0: 不抢； j = 1: 抢 (带状态）
- 状态是i的单个状态，不是0--i的整体状态
- 递推公式：
有可能连续几个房屋不抢
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) 取决于前一天的情况
dp[i][1] = dp[i-1][0] + nums[i]
- 复杂度. 时间：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, 不带状态
- dp[i]: 房屋0,...,i; 最高金额
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
第i个不抢 vs 抢 (第i-1个必然不抢, 所以由两天前的状态转移而来)
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]
- 可以空间优化
213. 打家劫舍 II
- 思路
- example
- 房屋围成一圈, 转化为两个问题I
- 第0个不抢，最后一个可能抢也可能不抢。转化为问题1,...,n-1
- 第0个抢，最后一个必然不抢。转化为问题0,...,n-2
注意指标映射关系以及corner case （1个2个元素的情况)
- 复杂度. 时间：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 （在树的结构上使用DP）
- 返回值包括 当前根节点的两种状态
- 复杂度. 时间：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))
