- 用两个数组(可以简化为两个数)来保存当前步偷和不偷的情况，下一步计算的时候用到前一步偷或不偷的结果。
- 当前步不偷的最大值，是前一步偷或者不偷的最大值(前一步不偷可能比前一步偷要大)
- 198题，动态规划
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
r = nums[0]
nr = 0
for money in nums[1:]:
pre_r = r
pre_nr = nr
# 当前步要偷的话,能获得当前的钱+前一步不偷的钱
r = pre_nr + money
# 当前步不偷的话,能获得最大的钱是前一步偷或者不偷的最大钱数
nr = max(pre_nr, pre_r)
return max(r, nr)
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 其实是两次动态规划的解法:
# 1.偷第一个房子的前提下执行一遍;2.不偷第一个房子的前提下执行一遍;
if len(nums) == 0:
return 0
# 初始化中多加一个len(nums)==1的情况
if len(nums) == 1:
return nums[0]
# 偷第一个房子的前提下想偷当前房子
rf_r = nums[0]
# 偷第一个房子的前提下不偷当前房子
# (注意初始化要为0,因为第一次偷第二个房子的时候,要用到这个数据,此时第一个房子不能偷)
rf_nr = 0
# 不偷第一个房子的前提下偷当前房子
nrf_r = 0
# 不偷第一个房子的前提下不偷当前房子
nrf_nr = 0
for money in nums[1:]:
pre_rf_r = rf_r
pre_rf_nr = rf_nr
pre_nrf_r = nrf_r
pre_nrf_nr = nrf_nr
rf_r = pre_rf_nr + money
rf_nr = max(pre_rf_r, pre_rf_nr)
nrf_r = pre_nrf_nr + money
nrf_nr = max(pre_nrf_r, pre_nrf_nr)
# 返回中间两种可能
return max(rf_nr, nrf_r)
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = self.helper(root)
return max(res[0], res[1])
def helper(self, root):
if not root:
return [0, 0]
left_res = self.helper(root.left)
right_res = self.helper(root.right)
# 偷当前结点:当前结点的结果+左孩子不偷的结果+右孩子不偷的结果
r = root.val + left_res[0] + right_res[0]
# 不偷当前结点:左孩子偷或不偷的最大值+右孩子偷或不偷的最大值
nr = max(left_res[0], left_res[1]) + max(right_res[0], right_res[1])
res = [nr, r]
return res
