Note to self

找出三的次方。 這邊有遞迴方法和迭代的方法。提示有說要不用迭代和遞迴解這題。 遞迴的方法如下： 迭代的方法如下：

找到二的次方，有很多方法，這邊我實作一個最常見的方法。 用n & n - 1，從二進制去看，如果是0就是二的次方。

這題很簡單，規則限定直接從root到leaf的總和。 直接用DFS遞迴解。 參考Path Sum III方法一樣，用一個pre去找。

看到這題，一開始的想法是level order travel，但是最後沒有做出來。 問題在於無法判斷同一條路上有2條以上的路徑。 後來發現有一個很猛的作法，用雙重遞迴。

首先我覺得這題有點難，level order, DFS, BFS要複習清楚！ 解題的思路：

強盜搶劫問題，首先依題目規定，一旦搶了i就不能搶i+1的房子了。 因此我們釐清一下，如何看到題目就知道要用DP去解呢？ DP又分為top-down和bottom-up， top-down顧名思義就是從大問題到小問題，bottom-up是從小問題到大問題，DP加入memorization的機制。 top-down通常是用遞迴觀念去看。bottom-up通常用陣列(or vector)去記憶初始的問題，再從小問題逐步和成大問題。 因此，題目可以這麼看。設i為index。rob[i]為最佳解。以ex. 2為例： rob[0] = 只有一間房子，故得最佳解，即2。 rob[1] = 從[2,7]當中挑出的最佳解，即7。 此時，要思考怎麼得出rob[2]呢？ rob[2] 先直接從肉眼看出[2,7,9] = 11，它等同於rob[2] = max(rob[2-1], 當前第i房子+ rob[2-2]) rob[i] = max(rob[i-1], 當前房子 + rob[i-2])