高端品牌包包都有哪些_腾讯企业邮箱申请_网站如何被百度快速收录_杭州百度公司在哪里

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] * lengthdp[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] * lengthdp[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%。搞定收工~