My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
HashMap<TreeNode, Integer> cache = new HashMap<TreeNode, Integer>();
public int rob(TreeNode root) {
if (root == null) {
return 0;
}
else if (cache.containsKey(root)) {
return cache.get(root);
}
int val = 0;
if (root.left != null) {
val += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
val += rob(root.right.left) + rob(root.right.right);
}
int max = Math.max(val + root.val, rob(root.left) + rob(root.right));
cache.put(root, max);
return max;
}
}
仔細(xì)研讀：
https://discuss.leetcode.com/topic/39659/easy-understanding-solution-with-dfs/2
這道題目沒做出來，然后看了答案，覺得這篇解析說的很棒搓译。
一開始的思路應(yīng)該是很自然的霉祸，但我卻沒有想到蚣旱。
rob(TreeNode root)
返回以當(dāng)前結(jié)點(diǎn)作為root墙贱，可以搶到的最多的錢您单。
這個(gè)結(jié)點(diǎn)实牡，可能偷陌僵，也可能沒偷。
那么這個(gè)rob(root) 的終止條件是什么创坞？
肯定是 root == null
那么遞推式呢碗短？
或者說，和下面層與層之間的關(guān)系如何確定呢题涨？
如果結(jié)點(diǎn)被搶了偎谁，那么不能偷left, right了总滩。
所以
rob(root) = rob(root.left.left) + rob(root.left.right) +
rob(root.right.left) + rob(root.right.right) + root.val;
注意，這里巡雨，
rob(root.left) + rob(root.right)
可能 =
rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right) + root.val;
如果 偷了root 左右闰渔，還沒有直接投 root 孫子賺得多
所以這里我們可以看出，這個(gè)dp铐望，狀態(tài)與狀態(tài)之間冈涧，互相聯(lián)系，
rob(root) 需要依靠rob(left.left), rob(left.right)
rob(left) 也需要 依靠 rob(left.left), rob(left.right)
重復(fù)就來了正蛙。下面再細(xì)說督弓。
從這里可以看出。
rob(root)
= root.val +
Math.max(
rob(root.left) + rob(root.right),
rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right)
);
遞推式有了跟畅，我們就可以一層層往下計(jì)算了咽筋。
其實(shí)也是 bottom up
然后發(fā)現(xiàn)速度特別慢，原因就是剛剛說的徊件，有很多東西都重復(fù)計(jì)算了奸攻，然后狀態(tài)之間互相焦灼，互相相關(guān)虱痕，有許多東西需要算好幾遍睹耐。
然后一個(gè)工程上的手段是，
剪枝
cut edge
剪枝的本質(zhì)有兩點(diǎn)部翘。
當(dāng)從當(dāng)前狀態(tài)下去硝训，以后無論如何變化，都不可能獲得我們需要的那個(gè)狀態(tài)的話新思，那就直接停止吧窖梁，不用走到無路可走的時(shí)候再回頭
cache，有些已經(jīng)計(jì)算過的最優(yōu)解夹囚，全部存在cache中纵刘。這樣下次要用的時(shí)候避免計(jì)算。
這里采用了方法二進(jìn)行了剪枝荸哟，于是有了上面的代碼假哎。
然后速度一下快多了。
**
但是鞍历，剪枝雖然可以很好的降低時(shí)間舵抹，但是無法降低時(shí)間復(fù)雜度。
也就是說劣砍，他可以把時(shí)間復(fù)雜度的常數(shù)系數(shù)降得很多惧蛹，但是無法從根本上改良這個(gè)算法。
導(dǎo)致的問題是：
1 . 當(dāng)數(shù)據(jù)量越來越大的時(shí)候，剪枝的dp仍然有極限香嗓，仍然會(huì)很快就出現(xiàn)延遲超長(zhǎng)的情況爵政。
2 . recursion會(huì)導(dǎo)致stack overflow,即使剪枝仍然需要進(jìn)入一層棧去取出cache，所以當(dāng)輸入數(shù)據(jù)變得越來越大的時(shí)候陶缺，剪枝也會(huì)很快爆棧
**
舉例：
1 . 斐波那契數(shù)列钾挟。
第一種做法，設(shè)置一個(gè)數(shù)組cache
long[] cache;
private int counter = 0;
private int hit = 0;
public long f(int n) {
counter = 0;
hit = 0;
if (n < 0) {
return 0;
}
cache = new long[n + 1];
cache[0] = 1;
return f(n - 1, cache) + f(n - 2, cache);
}
private long f(int n, long[] cache) {
counter++;
if (n < 0) {
return 0;
}
else if (cache[n] != 0) {
hit++;
return cache[n];
}
else {
long ret = f(n - 1, cache) + f(n - 2, cache);
cache[n] = ret;
return ret;
}
}
2 . iteration dp
public long f2(int n) {
if (n < 0) {
return 0;
}
else if (n < 2) {
return 1;
}
long pre = 1;
long next = 1;
for (int i = 2; i <= n; i++) {
long sum = pre + next;
pre = next;
next = sum;
}
return next;
}
然后測(cè)試相同的輸入下饱岸，時(shí)間的對(duì)比掺出，如下：
第一個(gè)點(diǎn)可以當(dāng)做噪音點(diǎn)，因?yàn)镃PU可能沒有引起足夠重視苫费，
所以 f(5) 跑的時(shí)間比 f(10) 還要大很多
但是看總體趨勢(shì)汤锨，我們還是可以發(fā)現(xiàn)，即使加了cache百框，當(dāng)輸入變大的時(shí)候闲礼，增大的趨勢(shì)，也是很陡峭的铐维。
而iteration增大的趨勢(shì)則是比較平緩的
為了做這個(gè)實(shí)驗(yàn)柬泽，破費(fèi)了些時(shí)間。
但畫出來后嫁蛇，發(fā)現(xiàn)竟然如此完美锨并。
perfect~
第二個(gè)例子就是 Burst Baloon了啊
但是說起來太久遠(yuǎn)了，具體可以看下這道題目在簡(jiǎn)書里我寫的文章睬棚。
總是 dp recursion >>> dp iteration
因?yàn)?dp recursion + memorization 不能從根本上解決問題第煮。
接著這道題目往下說。
所以抑党，我們需要把狀態(tài)和狀態(tài)之間完全獨(dú)立起來包警。
想斐波那契數(shù)列的iteration解法。
我求 f(n) 的時(shí)候不用再次計(jì)算 f(n - 1), f(n - 2),他們已經(jīng)完全計(jì)算好了底靠，完全獨(dú)立的害晦。
但是recursion + memorization 版本不是
f(n) needs f(n - 2), f(n - 1) 也需要 f(n - 2)
雖然有hit，但是仍然要再recursive call 一下
你認(rèn)為差不多苛骨？
那你錯(cuò)了篱瞎，看我畫的圖苟呐。
左邊是 f(10) recursion + memorization 版本
右邊是 f(10) iteration 版本
從圖中我們可以看出痒芝，
左側(cè)一共需要計(jì)算 2 * n + 1 個(gè)結(jié)點(diǎn)。
右側(cè)一共需要計(jì)算 n + 1 個(gè)結(jié)點(diǎn)
似乎數(shù)量級(jí)是差不多的牵素。
再仔細(xì)看严衬。
左側(cè)有 2 * n + 1個(gè) stack
右側(cè)，只有 1 個(gè)stack
無論 n 多么大笆呆，
iteration 永遠(yuǎn)只有一個(gè) stack
而 recursion + memorization 無論cache policy 設(shè)計(jì)的再怎么好请琳， stack的個(gè)數(shù)都會(huì)隨著n變大而 劇烈 變大
而大量的棧操作粱挡，會(huì)有入棧出棧，不僅對(duì)空間上要影響俄精，對(duì)時(shí)間影響也很大询筏。
**
這才是為什么， recursion + memorization 看上去計(jì)算次數(shù)和 iteration差不多竖慧，但卻慢那么多的嫌套，根本原因所在。
**
那么圾旨，如何面對(duì)dp類題目呢踱讨？
首先，就是什么時(shí)候用dp
當(dāng)題目出現(xiàn)求 最大最小最長(zhǎng)最短最優(yōu)的時(shí)候砍的，一定是用DP
然后痹筛，dp有多種思路，我記得的有廓鞠，
1 . divide and conquer, 劃成兩塊帚稠，分別繼續(xù)
2 . string 類型的，通過前一個(gè)狀態(tài)推導(dǎo)后一個(gè)床佳。
3 . buy and sell stock 那種翁锡，狀態(tài)機(jī)的
等等。
然后分析哪里存在重復(fù)計(jì)算夕土，然后用memorization 剪枝
這是第二步馆衔，也是想出DP后
用memorization cut edge
第三步，就是思考怨绣，為什么需要重復(fù)計(jì)算角溃？
因?yàn)闋顟B(tài)之間相互依靠的效果太明顯，不能完全切開篮撑。
或者說减细，當(dāng)前狀態(tài)不僅依靠之前的一個(gè)狀態(tài)，可能依靠之前的所有狀態(tài)赢笨。
那么我們需要一種機(jī)制未蝌，把狀態(tài)之間徹底切開。
比如茧妒，結(jié)點(diǎn)只可能被偷或者沒被偷萧吠。
如果 rob(root) 被偷，
那么桐筏， left, right 只能沒被偷纸型，就不用在計(jì)算他們了
如果， root沒被偷，那么 left狰腌， right可以被偷除破，也可以沒被偷
寫出了下面的解法：
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int rob(TreeNode root) {
if (root == null) {
return 0;
}
int[] ret = helper(root);
return Math.max(ret[0], ret[1]);
}
private int[] helper(TreeNode root) {
if (root == null) {
return new int[]{0, 0};
}
int[] left = helper(root.left);
int[] right = helper(root.right);
int[] ret = new int[2];
ret[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
ret[1] = root.val + left[0] + right[0];
return ret;
}
}
這個(gè)算法下，
root只會(huì)有 root.left and root.right 推導(dǎo)琼腔，
和下面的 孫子輩沒關(guān)系了瑰枫，不需要recursive call
而上面的算法，
root,
root.left, root.right
都需要 recursive call 一下這些孫子輩丹莲，雖然 cache hit也沒有用躁垛，總有棧的消耗。當(dāng)輸入變大圾笨，尤其層數(shù)變多時(shí)教馆，消耗是很驚人的。
當(dāng)然擂达，這里還是沒寫成 iteration的做法土铺，否則更優(yōu)。
Anyway, Good luck, Richardo! -- 09/09/2016
