打家劫舍。
0-1，但不是背包。稍微有点tricky的地方是初始化，但是只要递推出来了初始化也就知道怎么做了。
对于每一家，判断：
因为依赖dp[i-2]和dp[i-1]，所以肯定得至少先初始化两个元素。
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
dp = [nums[0],max(nums[0],nums[1])]+[0]*(len(nums)-2)
for i in range(2, len(nums)):
dp[i] = max(nums[i]+dp[i-2], dp[i-1])
return dp[-1]
成环的情况一般分类讨论：假设nums[0,1,2,3,4].
最后再max一下即可。
def rob(self, nums: List[int]) -> int:
def acyclicRob(nums):
if len(nums) == 1:
return nums[0]
dp = [nums[0],max(nums[0],nums[1])]+[0]*(len(nums)-2)
for i in range(2, len(nums)):
dp[i] = max(nums[i]+dp[i-2], dp[i-1])
return dp[-1]
if len(nums) == 1:
return nums[0]
return max(acyclicRob(nums[1:]), acyclicRob(nums[:-1]))
二叉树，第一反应就是recursion+memoization。
如果root被抢，那就不能抢root的孩子。使用一个函数参数来表示root的可被抢状态。
以下代码一气呵成：
def rob(self, root: TreeNode) -> int:
memo = {}
def robHelper(root, canRob):
if not root:
return 0
if (root, canRob) in memo:
return memo[(root, canRob)]
res = 0
if canRob:
res = max(root.val+robHelper(root.left, False)+robHelper(root.right, False), robHelper(root.left, True)+robHelper(root.right, True))
else:
res = robHelper(root.left, True)+robHelper(root.right, True)
memo[(root, canRob)] = res
return res
return robHelper(root, True)
虽然跑通了，但运行时间并不美好。
这题做的过程中一下让我想起了贪心5里面讲过的968.监控二叉树。当时我也是用了recursion并向函数传入状态参数，结果完美超时。当时的DP解法是后序遍历，从底向上计算状态。那么这题是不是也能这么搞一下呢？
设：
根据分析：
初始化：如果root是None，a=b=c=0完事。
def rob(self, root: TreeNode) -> int:
def postorder(root):
if not root:
return 0,0,0
la, lb, lc = postorder(root.left)
ra, rb, rc = postorder(root.right)
a = lb+rb+root.val
b = lc+rc
c = max(a, b)
return a,b,c
return postorder(root)[2]
时间复杂度从O(2^n)瞬间变成O(n)，是不是觉得很棒棒呢。