198.打家劫舍
dp[i]代表着对于下标0到i的房间，能偷盗的最大金额。
class Solution:
def rob(self, nums: List[int]) -> int:
length = len(nums)
if length == 1:
return nums[0]
if length == 2:
return max(nums[0], nums[1])
dp = [0] * length
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, length):
# 偷第i家房间，那么一定没偷第i-1家房间，所以金额是dp[i-1]+nums[i]
# 不偷第i家房间，金额和dp[i-1]是一样的，在这不管第i-1家房间偷了没。
dp[i] = max(dp[i-2]+nums[i], dp[i-1])
return dp[length-1]
效率：0ms，击败100.00%
213.打家劫舍Ⅱ
class Solution:
def rob(self, nums: List[int]) -> int:
def rob_with_linear(nums: List[int]) -> int:
length = len(nums)
dp = [0] * length
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, length):
dp[i] = max(dp[i-2]+nums[i], dp[i-1])
return dp[length-1]
length = len(nums)
if length == 1:
return nums[0]
if length == 2:
return max(nums[0], nums[1])
# 不考虑尾元素
situation1 = rob_with_linear(nums[:-1])
# 不考虑首元素
situation2 = rob_with_linear(nums[1:])
return max(situation1, situation2)
效率：0ms，击败100.00%
337.打家劫舍Ⅲ（(╬▔皿▔)凸）
太特喵恶心了这题……居然不是
hard……别偷了哥，求求你别偷了……我直接给你钱可以不……完全没思路，完全没想到怎么用dp做。最后发现其实dp[2]就相当于一个memo[2]，感觉跟动态规划其实没毛线关系啊。就是记忆化存储优化递归啊……sb的我一开始还在想是不是要用中序遍历，然后就卡死在状态转移上了。
这道题的重点在于用了递推，那么就没必要使用dp数组存储全部节点的状态了，只需要用dp数组存储当前节点的状态，然后状态转移就是自然而然递归下去即可。
其次就是关于遍历顺序，为什么是后序遍历呢？因为根节点的值取决于其左右孩子的值，所以是后序遍历。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
# dp[0]代表着不偷当前节点时的最大金额。dp[1]代表着偷了当前节点时的最大金额。
def robtree(cur:TreeNode) -> [int]:
if cur == None:
return [0,0]
# 计算出当前节点左孩子和右孩子分别的dp状态
leftdp = robtree(cur.left)
rightdp = robtree(cur.right)
# 不偷当前节点。那么能获得的最大金额就全部来自于左右孩子
not_rob = max(leftdp[0],leftdp[1])+max(rightdp[0], rightdp[1])
# 偷了当前节点，那么最大金额=当前节点金额+左孩子不偷时的金额+右孩子不偷时的金额
robbed = cur.val+leftdp[0]+rightdp[0]
return [not_rob, robbed]
rootdp = robtree(root)
return max(rootdp[0],rootdp[1])
效率：7ms，击败39.03%
其实还是不高啊……可是这已经是一个典型的树形DP解法了，时间复杂度是O(n)，因为每个节点只访问一次。空间复杂度的话，递归的栈空间是O(h)，h是树的高度，这应该已经是最优的了。
再仔细看了下代码，okkk，原来是max函数调用了多次，而且也可以将数组改为元组。
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
# dp[0]代表着不偷当前节点时的最大金额。dp[1]代表着偷了当前节点时的最大金
def robtree(cur:TreeNode) -> tuple:
if cur == None:
return (0,0)
# 计算出当前节点左孩子和右孩子分别的dp状态
leftdp = robtree(cur.left)
rightdp = robtree(cur.right)
# 不偷当前节点。那么能获得的最大金额就全部来自于左右孩子
not_rob = max(leftdp)+max(rightdp)
# 偷了当前节点，那么最大金额=当前节点金额+左孩子不偷时的金额+右孩子不偷时的金额
robbed = cur.val+leftdp[0]+rightdp[0]
return (not_rob, robbed)
return max(robtree(root))
效率：3ms，击败91.46%。搞定收工~