leetcode337. 打家劫舍 III(樹狀dp)

在上次打劫完一條街道之後和一圈房屋後，小偷又發現了一個新的可行竊的地區。這個地區隻有一個入口，我們稱之為“根”。 除了“根”之外，每棟房子有且隻有一個“父“房子與之相連。一番偵察之後，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個直接相連的房子在同一天晚上被打劫，房屋将自動報警。

計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。

輸入: [3,2,3,null,3,null,1]

     3

    / \

   2   3

    \   \ 

     3   1

輸出: 7 

解釋: 小偷一晚能夠盜取的最高金額 = 3 + 3 + 1 = 7

回憶一下，在打家劫舍1中，我們一維數組dp[i] 來代表以第i個房子結尾時小偷能偷的最多的錢。這裡換個思路，對于每一個節點，可以選擇偷或者不偷，兩種不同的情況：我們用 f[i] 代表 i 節點被選擇時 i 的子樹可以偷到的最大金額；用 g[i] 代表 i 節點沒有被選擇時 i 的子樹可以偷到的最大金額。

大佬這麼解釋：

在設計狀态的時候，在後面加一維，消除後效性，就是二維數組，dp[i][j]——j=0就是不偷，j=1就是偷

但是之前的dp都是用數組來存儲，這裡樹是非線性的。是以這裡我選的資料結構是哈希表，map<TreeNode*,int>

再來思考他們的動态轉移方程：

1. f[i] = g[i->left]+g[i->right]
2. g[i] = max(f[i->left]+i->left->val,g[i->left]) + max(f[i->right]+i->right->val,g[i->right])

第一個方程很好了解，既然選擇了目前節點，他的兒子們都不能選

對于第二個方程的解釋如下：

目前節點不能選，是以他的兒子都可以選，并且左兒子和右兒子是互不幹擾的是以首先可以确定的是，目前的結果就是左邊+右邊

再來具體看某一個兒子（假設是 r），這裡和打家劫舍1中一樣的想法，r可以選擇偷，也可以不偷，設想這種情況：r是1塊錢，但是r的兒子有1億，是以我們就需要作出選擇，從偷r（f[i->left]+i->left->val）和不偷r（g[i->left]）中挑出最大值就可以了。

在寫代碼的時候要注意空指針就可以了

ac代碼如下：

class Solution {
public:
    void dfs(TreeNode* root,map<TreeNode*,int>& f,map<TreeNode*,int>& g){
        if(root==NULL) return;
        dfs(root->left,f,g);
        dfs(root->right,f,g);
        f[root] = g[root->left]+g[root->right];
        int l = 0,r =0;
        if(root->left!=NULL)
            l = max(f[root->left]+root->left->val,g[root->left]);
        else l = 0;
        if(root->right!=NULL)
            r = max(f[root->right]+root->right->val,g[root->right]);
        else r = 0;
        g[root] = l + r;
        return;
    }
    int rob(TreeNode* root) {
        if(root==NULL) return 0;
        map<TreeNode*,int> f; //yes
        map<TreeNode*,int> g; //no
        dfs(root,f,g);
        return max(f[root]+root->val,g[root]);
    }
};