https://leetcode.cn/problems/house-robber-iii/description/
前言
建議還是先看看動態規劃的基礎題再看這個。動態規劃是不刷題，自己100%想不出來的。
基礎題：
- 23
小白想法
現在我們想遍歷的數據結構不是數組了，而是一顆樹。在樹上的dp叫做“樹形dp”（so called）。
那在遍歷尋找解更新dp的時候無非就是用遍歷樹的dfs那一套了，不再是for i in range(length)了。
現在不方便用dp數組去存儲dp的值了，畢竟這是個樹。那用什么？我們之前之所以用數組，是因為使用dp[i]能夠直接取到遍歷到nums[i]時dp的值，之前的dp數組實際上充當的是一個hash table（字典、map…隨便你怎么叫）的作用。 那我們就直接用字典就好啦！不再用數組了。
然后能不能像for i in range(length)一樣“從前往后”邊遍歷邊更新？樹上的“從前往后”是什么？是從葉子走向根。
有了前幾點的鋪墊，下面正式進入狀態轉移方程的構建。
還能不能像以前“打家劫舍”那個題一樣通過選擇前幾個狀態來更新dp？
看上去好像可以。但是請注意我們現在的“dp數組”不是數組了，而是一個字典。字典的key是node，value是dp值。如果是數組，我們可以很方便的通過i-1,i-2指針來訪問前面的狀態，但是此時的字典已經不適合了。 當前的狀態i和前面時刻-2的“聯系”已經沒有了。
題外話，莫非我可以先把“樹形”的數據先壓成一個數組，然后再套用之前的思路？想法很好，甚至也能做，但是寫起來比較麻煩，下一個！
就算是有聯系，在當前節點時，需要考慮 自己2個孩子是否被偷，沒偷就有可能跟孫子一起被偷，共計6個節點，我相信寫起來也挺復雜，要max很多次。
dead end after all…
題解，學習
換個dp數組的意義吧！我們不拘泥于過去的思路了。
在之前做“最大連乘子數組”的時候我們不是也用了2個dp數組嗎？
把dp拆開成2個，分成 選擇了子節點的最大值，和沒選擇了子節點的最大值。請注意樹上的“從前往后”是從葉子到根。把這2個dp分別叫做dp_selected和dp_unselected。
先考慮最簡單的情況，從最前面開始，只有一個葉子的時候，2個dp的值很好知道，葉子值或者0。
而當到了樹上的分支now的時候，dp_selected[now]的意義是選擇當前節點，那么應該等于自己當前節點的值+沒選自己孩子的最大dp值：now.val+dp_unselected[now.left]+dp_unselected[now.right]，只有這 一種情況，是因為相鄰的父子不能一起選；而dp_unselected[now]就比較多了：由于我當前節點沒選擇，那么我的孩子可以選，也可以不選，那我要當前最大的，要取他們的最大值更新。
上面寫的比較“大白話”，我個人感覺用數學公式表達起來比較簡潔易懂。。
以下為官方題解
:
# self.val = val
# self.left = left
# self.right = right
class Solution:def rob(self, root: Optional[TreeNode]) -> int:# dp的存儲形式變了，變成字典# dp的意義變了，不再是“以xx結尾的結果”from collections import defaultdictdp_selected,dp_unselected=defaultdict(int),defaultdict(int)def travel_tree(now):if now is None:return travel_tree(now.left)travel_tree(now.right)left=now.leftright=now.rightres1=now.val+dp_unselected[left]+dp_unselected[right]res2=max(dp_selected[left],dp_unselected[left])+max(dp_selected[right],dp_unselected[right])dp_selected[now]=res1# 可以選擇不更新，因為不更新他就是0# 在節點選擇的過程中，0是肯定會被丟棄的dp_unselected[now]=res2return travel_tree(root)return max(dp_selected[root],dp_unselected[root])
defaultdict的作用是給予在dict中不存在的key一個初始值，簡化代碼。
提交，過了。
想不出來，不刷題真的想不出來。
優化
顯然dp的hash table是很重要的，但是我們能不能把他也優化掉，不使用他的額外的空間呢？
我們可以從轉移方程看到，當前點的更新只跟自己孩子的那幾個值有關。
這熟悉的配方！在dp[i]只跟dp[i-1]有關時，我們也能通過類似的方法只保留上一個dp的值來優化空間。
那么怎么只保留上一個dp的值呢？我們上一個dp的值是“選左孩子的最大值”、“不選左孩子的最大值”、“選右孩子的最大值”、“不選右孩子的最大值”，一共4個，使用函數返回給父節點就可以了！（畢竟除了使用額外的空間，函數返回值是唯一父子能交流的東西了）
class Solution:def rob(self, root: Optional[TreeNode]) -> int:def travel_tree(now):if now is None: return 0, 0 l_rob, l_not_rob = travel_tree(now.left)r_rob, r_not_rob = travel_tree(now.right)rob = l_not_rob + r_not_rob + node.val # 選not_rob = max(l_rob, l_not_rob) + max(r_rob, r_not_rob) # 不選return rob, not_robreturn max(travel_tree(root)) # 根節點選或不選的最大值
