題目鏈接

打家劫舍 III

題目描述

注意點(diǎn)

• 如果 兩個直接相連的房子在同一天晚上被打劫 ，房屋將自動報警
• 返回 在不觸動警報的情況下 ，小偷能夠盜取的最高金額

解答思路

• 記憶化 + 解決重復(fù)子問題解決本題，在任意一個位置，小偷可以選擇打劫該房屋和不打劫該房屋，如果打劫，則不能打劫該節(jié)點(diǎn)下的子節(jié)點(diǎn)，如果不打劫，則該節(jié)點(diǎn)下的子節(jié)點(diǎn)可以選擇打劫也可以選擇不打劫，可以轉(zhuǎn)換為動態(tài)規(guī)劃的問題：任意一個位置處能夠盜取的最大金額為其子節(jié)點(diǎn)能夠盜取的最大金額之和或其本身加上其孫子節(jié)點(diǎn)能夠盜取的最大金額之和的最大值，為了防止同一個節(jié)點(diǎn)的最大金額重復(fù)計(jì)算，可以使用Map存儲每個節(jié)點(diǎn)的最大金額
• 參考題解在任意一個節(jié)點(diǎn)時，可以用大小為2的數(shù)組result存儲該節(jié)點(diǎn)的兩種情況：也就是result[0]為不搶劫該節(jié)點(diǎn)的最大金額，result[1]為搶劫該節(jié)點(diǎn)的最大金額

代碼

方法一：

class Solution {
    public int rob(TreeNode root) {
        Map<TreeNode, Integer> map = new HashMap<>();
        return robInterval(root, map);
    }

    public int robInterval(TreeNode root, Map<TreeNode, Integer> map) {
        if (root == null) {
            return 0;
        }
        if (map.get(root) != null) {
            return map.get(root);
        }
        int money = root.val;
        if (root.left != null) {
            money = money + robInterval(root.left.left, map) + robInterval(root.left.right, map);
        }
        if (root.right != null) {
            money = money + robInterval(root.right.left, map) + robInterval(root.right.right, map);
        }
        int maxVal = Math.max(money, robInterval(root.left, map) + robInterval(root.right, map));
        map.put(root, maxVal);
        return maxVal;
    }
}

方法二：文章來源地址http://www.zghlxwxcb.cn/news/detail-708418.html

// 優(yōu)化版
class Solution {
    public int rob(TreeNode root) {
        // 0不搶劫，1搶劫
        int[] result = robInternal(root);
        return Math.max(result[0], result[1]);
    }

    public int[] robInternal(TreeNode root) {
        if (root == null) {
            return new int[2];
        }
        int[] leftVal = robInternal(root.left);
        int[] rightVal = robInternal(root.right);
        int[] result = new int[2];
        result[0] = Math.max(leftVal[0], leftVal[1]) + Math.max(rightVal[0], rightVal[1]);
        result[1] =  root.val + leftVal[0] + rightVal[0];
        return result;
    }
}

關(guān)鍵點(diǎn)

• 動態(tài)規(guī)劃的思想

到了這里，關(guān)于打家劫舍 III的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！