這一篇也是基於"打家劫舍"的擴展，需要針對特殊情況特殊考慮，當然其本質還是動態規劃，優化時需要考慮數據結構。

原題

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

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

示例 1:

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

     3
    / \
   2   3
    \   \
     3   1

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

示例 2:

輸入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \
 1   3   1

輸出: 9
解釋: 小偷一晚能夠盜取的最高金額 = 4 + 5 = 9.

原題url：https://leetcode-cn.com/problems/house-robber-iii/

解題

先給出樹節點的結構：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

簡單思路

這道題簡單來說，就是如果存在 父節點、子節點、孫子節點 三層的話，要麼偷 父節點 + 孫子節點 ，要麼只偷 子節點 。

順着這個思路，我們只要找出每個節點所能偷到的最大值，自然也就能找出從 root 節點開始偷的最大值了。

接下來我們看看代碼：

class Solution {

    Map<TreeNode, Integer> cache = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 是否已經計算過
        if (cache.containsKey(root)) {
            return cache.get(root);
        }

        // 策略1：搶當前節點和孫子節點
        int sum1 = root.val +
            // 左子節點的子節點們
            (root.left == null ? 0 : (rob(root.left.left) + rob(root.left.right))) +
            // 右子節點的子節點們
            (root.right == null ? 0 : (rob(root.right.left) + rob(root.right.right)));
        // 策略2：只搶子節點
        int sum2 = rob(root.left) + rob(root.right);
        // 找出更大的值
        int sum = Math.max(sum1, sum2);
        // 並記錄
        cache.put(root, sum);
        return sum;
    }
}

提交OK，執行用時： 5 ms ，只戰勝了 52.00% 的 java 提交記錄，因此還是有值得優化的地方。

優化

上面的解法，如果說有什麼值得優化的地方，就是在於我們在動態規劃時，不僅考慮了子節點，甚至也考慮到了孫子節點，因此當 子節點 變成 父節點 之後，孫子節點 也變成了 子節點。

也就是說，一開始的 孫子節點 被計算了兩遍。雖然我們借用了一個 map 來記錄了中間結果，但我們需要注意，這種情況依舊會被計算，只是代價被轉移到了針對 map 的操作，這也是需要消耗時間的。

那麼現在的優化，就轉變成針對中間狀態的記錄上了。

其實我們針對每個節點的狀態，只需要記錄兩種情況：搶或者不搶。而且這個狀態只會被父節點用到，並不需要永久保留。因此我們考慮用一個長度爲 2 的數組進行記錄，這樣就會快捷很多。

接下來我們看看代碼：

class Solution {
    public int rob(TreeNode root) {
        // index爲0，代表不搶當前節點的最大值
        // index爲1，代表搶當前節點，不搶子節點的最大值
        int[] res = dp(root);
        return Math.max(res[0], res[1]);

    }

    public int[] dp(TreeNode cur) {
        if(cur == null) {
            return new int[]{0,0};
        }

        int[] left = dp(cur.left);
        int[] right = dp(cur.right);
        // 搶當前節點，子節點都不搶
        int rob = cur.val + left[0] +right[0];
        // 不搶當前節點，獲取左右子節點各自的最大值
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        // 返回結果
        return new int[]{notRob, rob};

    }
}

提交OK，時間消耗只有 1 ms ，確實快了很多。

總結

以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要還是利用動態規劃，只是需要大家進行思路轉化，優化時需要考慮的更多是對數據結構的理解。

有興趣的話可以訪問我的博客或者關注我的公衆號，說不定會有意外的驚喜。

https://death00.github.io/

公衆號：健程之道

點擊此處留言

相關文章