力扣337——打家劫舍 III 頭條網

2020-11-07 07:51:11 佚名

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

原題

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

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

示例 1:

<code>輸入:
 [3,2,3,null,3,null,1]

     3
    /
 \
   2
   3
    \
   \ 
     3
   1

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

示例 2:

<code>輸入:
 [3,4,5,1,3,null,1]

     3
    /
 \
   4
   5
  /
 \
    
\ 
 1
   3
   1

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

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

解題

先給出樹節點的結構：

<code>public
 
class
 TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode( 
int x) { val = x; }
}/<code>

簡單思路

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

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

接下來我們看看代碼：

<code>
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);
        }

         
        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)));
         
        int sum2 = rob(root.left
) + rob(root.right);
         
        int sum = Math
.max(sum1, sum2);
         
        cache.put(root, sum);
        return sum;
    }
}/<code>

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

優化

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

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

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

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

接下來我們看看代碼：

<code>class
 Solution {
    
public
 int
 rob
(TreeNode root) {
         
         
        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};

    }
}/<code>