九章演算法 | Uber面試題2 : House Robber III

撰文 | JZ

專欄 | 九章演算法

題目描述

小偷找到了一個新的偷盜地點，這裡地區的房子組成了一棵二叉樹，地區的入口是二叉樹的根所在的房子。如果小偷同時偷竊了兩個直接相鄰的房子，就會觸發警報器。求在不觸發警報器的情況下小偷可以搶到的最多的money。

Example：

3

/

2 3

3 1

小偷可以搶到的最多的money是3+3+1=7（偷竊帶下劃線的房子）

演算法分析

本題是House Robber的follow up。House Robber-i中房子排列成一個序列，House Robber-ii中房子排列成一個環，均可以用動態規劃解決。

這裡簡單分析一下房子排成一個序列的情況，直覺上我們應該盡量偷價值高的房子，但因為有限制條件不能偷相鄰的房子，直接貪心不可行。考慮動態規劃，如果我們已知前k個房子可能偷到的最高價值，當k等於n時我們也就得到了全局最優解；同時，前k個房子能偷到的最高價值可以通過對第k個房子做決策（偷或者不偷），從比k小的局部最優解中得到。

對於本問題，由於是樹上的問題， 我們有一種dp類型是，在樹上一邊搜索，一邊利用dp數組保存狀態，所以我們叫他樹形dp，這是一類型大家沒怎麼見過的新題型。假設我們已知了根節點的左右子樹的局部最優解，通過對根節點所在的房子進行決策：偷或者不偷，我們就可以得到全局最優解。具體演算法過程如下： 遞歸先求得左右子樹的局部最優解，分別表示該子樹根節點的房子偷和不偷所能得到的最高價值，再得到了左右子樹的返回值後，對於本層更新，我們需要考慮，1.左右兒子不偷的時候我們當前可以偷本層，2.左右兒子都偷的時候我們當前本層則不能偷。

具體動態規劃四要素為：

Definition:

dp[i][0]表示以i為根的子樹不偷根節點能獲得的最高價值，dp[i][1]表示以i為根的子樹偷根節點能獲得的最高價值

Function:

dp[i][0] = max(dp[left[i]][0], dp[left[i]][1]) + max(dp[right[i]][0], dp[right[i]][1]);

dp[i][1] = dp[left[i]][0] + dp[right[i]][0];

Intialize:

空節點的dp值均為0

Answer:

dp[root][0]和dp[root][1]中的較大值

最後返回根節點的兩個dp值中較大的那個即可。

參考程序

面試官角度分析

本題可以用搜索解決，但面試官考察的是對樹和動態規劃的理解。給出基於動態規劃思想的O(n)可達到hire的程度，n為總房子數。

LC 相關練習題目

https://lintcode.com/problems/house-robber/

https://lintcode.com/problems/house-robber-ii/

推薦閱讀：