在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個新的可行竊的地區(qū)。這個地區(qū)只有一個入口，我們稱之為“根”。 除了“根”之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。

計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。

示例 1:

輸入: [3,2,3,null,3,null,1]

3/ \2 3\ \ 3 1

輸出: 7
解釋: 小偷一晚能夠盜取的最高金額 = 3 + 3 + 1 = 7.

示例 2:

輸入: [3,4,5,1,3,null,1]

3/ \4 5/ \ \ 1 3 1

輸出: 9
解釋: 小偷一晚能夠盜取的最高金額 = 4 + 5 = 9.

動態(tài)規(guī)劃

簡化一下這個問題：一棵二叉樹，樹上的每個點都有對應的權值，每個點有兩種狀態(tài)（選中和不選中），問在不能同時選中有父子關系的點的情況下，能選中的點的最大權值和是多少。

我們可以用 f(o) 表示選擇 o 節(jié)點的情況下，o 節(jié)點的子樹上被選擇的節(jié)點的最大權值和；g(o) 表示不選擇 o 節(jié)點的情況下，o 節(jié)點的子樹上被選擇的節(jié)點的最大權值和；l 和 r 代表 o 的左右孩子。

• 當 o 被選中時，o 的左右孩子都不能被選中，故 o 被選中情況下子樹上被選中點的最大權值和為 l 和 r 不被選中的最大權值和相加，即 f(o)=g(l)+g?。
• 當 o 不被選中時，o 的左右孩子可以被選中，也可以不被選中。對于 o 的某個具體的孩子 x，它對 o 的貢獻是 x 被選中和不被選中情況下權值和的較大值。故 g(o)=max{f(l),g(l)}+max{f?,g?}。

Code

def rob(self, root: TreeNode) -> int:def _rob(r):if not r:return 0, 0ls, ln = _rob(r.left)rs, rn = _rob(r.right)return r.val + ln + rn, max(ls, ln) + max(rs, rn)return max(_rob(root))

總結

以上是生活随笔為你收集整理的337. House Robber III 打家劫舍 III的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。