Leetcode 上的小偷太難了！！
周末日常。
題目介紹
這是 House Robber III。
這道題和之前兩個版本最大不同在于引入了二叉樹。 樹的每個節(jié)點(具體的房子)都有對應的值(金額)。每個節(jié)點有兩種狀態(tài)，偷或者不偷。 規(guī)則是不能同時偷父子節(jié)點， 
比如上圖，如果選擇偷 A 節(jié)點，那么 B 和 C 就不能偷，既然 B 和 C 不能偷，那么 DEFG 就可以偷的。 因為 DEFG 和 A 是子孫關系，而不是父子關系。
這樣的背景下，求小偷能偷的最大金額?
暴力遞歸
我們還是用上圖的那個例子。我們可以直接求出最大金額,偽代碼如下，
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// 求當前A節(jié)點能偷的最大金額res
// 偽代碼
item := node.Val + node.Left.Left.Val + node.Left.Right.Val +
node.Right.Left.Val + node.Right.Right.Val
res := max(item, node.Left.Val+node.Right.val)實際中，DE 是 B 的子節(jié)點，DE 也會變成別人的父節(jié)點，甚至是爺爺節(jié)點。
對于任意一個節(jié)點，求對應能偷的最大值本質(zhì)就是上述的代碼，我們需要改成遞推公式。
// 遞推公式偽代碼
func rob(node *TreeNode) int {
item1 := node.Val + rob(node.Left.Left) + rob(node.Left.Right) +
rob(node.Right.Left) + rob(node.Right.Right)
res := max(item1, rob(node.Left)+rob(node.Right))
}然后我們就可以翻譯上面的代碼,
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rob(root *TreeNode) int {
if root == nil {
return 0
}
money := root.Val
if root.Left != nil {
money += (rob(root.Left.Left) + rob(root.Left.Right))
}
if root.Right != nil {
money += (rob(root.Right.Left) + rob(root.Right.Right))
}
res := max(money, rob(root.Left)+rob(root.Right))
return res
}
func max(item1, item2 int) int {
if item1 >= item2 {
return item1
}
return item2
}要是這樣直接運行，Leetcode 一般會報以下錯誤。
存在大量重復計算節(jié)點。比如在計算 A 節(jié)點的值時，會計算BC，同時也會計算 DEFG 的值。 這種情況下，當計算 BC 的時候，又會重新計算一遍 DEFG......
沒什么是加緩存解決不了的。
記憶化遞歸
它也有個高大上的名字，叫記憶化遞歸。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var cache map[*TreeNode]int
func init() {
cache = make(map[*TreeNode]int)
}
func rob(root *TreeNode) int {
if root == nil {
return 0
}
if item, ok := cache[root]; ok {
return item
}
money := root.Val
if root.Left != nil {
money += (rob(root.Left.Left) + rob(root.Left.Right))
}
if root.Right != nil {
money += (rob(root.Right.Left) + rob(root.Right.Right))
}
res := max(money, rob(root.Left)+rob(root.Right))
cache[root] = res
return res
}
func max(item1, item2 int) int {
if item1 >= item2 {
return item1
}
return item2
}動態(tài)規(guī)劃
那么，如何用動態(tài)規(guī)劃的思想解這道題？
動態(tài)規(guī)劃最重要的兩步:
定義狀態(tài)
狀態(tài)轉(zhuǎn)移方程
首先是狀態(tài)。 針對每一個節(jié)點，都只有兩種狀態(tài)，偷或者不偷。 在這個基礎上，我們可以進一步的保存每一個狀態(tài)偷或者不偷情況下當前最大金額值。
假設當前是 q 節(jié)點。 我們用 q[0] 表示選擇偷 q 節(jié)點的情況下當前最大金額值。用 q[1] 表示不選擇偷 q 節(jié)點的情況下當前最大金額值。即:
// 偽代碼
// 不偷q
q[0]=xxx
// 要偷q
q[1]=xxx那么最終我們只需要:
// 最大值偽代碼
max(q[0],q[1])接著就是狀態(tài)轉(zhuǎn)移方程。
假設 l 和 r 分別代表 q 的左右子節(jié)點。 那么，就會有以下公式:
當偷 q 時，q 的左右子節(jié)點不能被偷，那么偷 q 情況下最大總金額 = q 自身的值 +不能被偷的 l 和 r 位置最大金額值的和。即，
// 偽代碼
q[0]=q.val+l[1]+r[1]當不偷 q 時，q 的左右子節(jié)點都能偷。但是不一定要去偷。這取決于要偷和不偷情況下哪個金額更多。即:
// 偽代碼
q[1]=max(l[0],l[1])+max(r[0],r[1])這樣的話就可以翻譯代碼了。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rob(root *TreeNode) int {
val := df(root)
return max(val[0], val[1])
}
func df(root *TreeNode) [2]int {
var res [2]int
// 遞歸出口
if root == nil {
return [2]int{0, 0}
}
l, r := df(root.Left), df(root.Right)
// 選中當前節(jié)點情況下最大值
res[0] = root.Val + l[1] + r[1]
// 不選擇當前節(jié)點情況下最大值
res[1] = max(l[0], l[1]) + max(r[0], r[1])
return res
}
func max(item1, item2 int) int {
if item1 >= item2 {
return item1
}
return item2
}推薦閱讀