©2020-2024 ioDraw All rights reserved,
Privacy Policy
打家劫舍问题关键在于找到前后之间的依存关系。打家劫舍I-II在前一天的文章中有讲解到今天主要解决打家劫舍III，本题目为树形dp的入门问题。
<>198.打家劫舍
<>213.打家劫舍II
头尾相接的情况：将头尾取出来，然后单独看两种情况下的能够偷取的最大价值。
<>337.打家劫舍III-树形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: #
暴力法就是遍历所有的情况,不断递归考察所有的情况 if not root: return 0 if not root.left and not root.
right: return root.val # rob val1 = root.val if root.left : val1 += self.rob(
root.left.left) + self.rob(root.left.right) if root.right : val1 += self.rob(
root.right.left) + self.rob(root.right.right) # no rob val2 = self.rob(root.left
) + self.rob(root.right) return max(val1,val2)
<>动态规划
* 二叉树问题首先确定遍历顺序，本问题需要将叶子结点的状态确定下来，才能逐步向上进行遍历。
* 为每一个结点设置一个状态转义数组{偷，不偷}，最后返回根节点的最大钱币数量，获得两种根节点的状态即可。
* dp数组变化的含义： 每一个结点都有一个dp数组的变化状态dp[0]表示不偷该结点时的最大价值，dp[1]表示偷该结点时的最大价值。 //
有偷或者不偷两种状态 vector<int> robtree (TreeNode *cur){ // 本题使用的后续遍历，左右中 if(cur==null)
return vector<int>{0,0}; // 只有两个结果，取偷或者不偷的最大价值，首先是偷当前结点得到的钱币最大数量 vector<int>
leftdp= robtree(cur.left) vector<int> rightdp = robtree(cur.right) //处理中间结点
//偷当前结点与不偷叶子结点的最大价值之和 int val1 = cur.val + leftdp[0] + rightdp[0] //
不偷当前结点则需要考虑是否偷取叶子结点 int val2 = max(leftdp[0],leftdp[1]) + max(rightdp[0],rightdp
[1]) return {val1,val2} } # 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: def robtree(node): if not node: return [0,0] left =
robtree(node.left) right = robtree(node.right) # rob val1 = max(left[0],left[1]
) + max(right[0],right[1]) # no rob val2 = node.val + left[0] + right[0] return
[val1,val2] result = robtree(root) return max(result)