[数据结构与算法]【Leetcode】打家劫舍

题目链接：198. House Robber? ??213. House Robber II? ? ?337. House Robber III

1、打家劫舍I

相邻两家不能同时打劫，dp[i]表示打劫到第i家能够盗取到的最高金额。用动态规划，状态转移方程为：dp[i]=max(dp[i-2]+nums[i],dp[i-1])

因为求dp[i]只需用到前面两个数dp[i-1],dp[i-2]，所以可以不用数组，直接用两个变量表示即可。

代码如下：

var rob = function (nums) {
    const length = nums.length;
    if (length == 1)
        return nums[0];
    if (length == 2)
        return Math.max(nums[0], nums[1]);
    let first = nums[0], second = Math.max(nums[0], nums[1]);
    for (let i =  2; i < length; i++) {
        let temp = second;
        second = Math.max(nums[i] + first, second);
        first = temp;
    }
    return second;
}

2、打家劫舍II

所有房屋连成一个环，相邻两家不能同时打劫，第一家和最后一家相邻，肯定只能打劫一个。

那么就分成两种情况，1）打劫第1家，最后一家一定不能打劫。2）不打劫第1家，最后一家可以打劫也可以不打劫。其余和“打家劫舍I”相同，求这两种情况的较大者就是最终的值。

代码如下：

var rob = function (nums) {
    const length = nums.length;
    if (length == 1)
        return nums[0];
    if (length == 2)
        return Math.max(nums[0], nums[1]);
    return Math.max(compare(0, length - 2, nums), compare(1, length - 1, nums));
    // 打家劫舍I的解题思路
    function compare(start, end, nums) {
        let first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for (let i = start + 2; i <= end; i++) {
            let temp = second;
            second = Math.max(nums[i] + first, second);
            first = temp;
        }
        return second;
    }
};

3、打家劫舍III

所有家庭组成一棵二叉树，直接相连的家庭不能都被打劫，即若父节点被打劫，那么直接相连的两个子节点都不能被打劫，若父节点不被打劫，那么直接相连的两个子节点都可以被打劫，也可以不被打劫。

用f(node)表示node节点被打劫，从该节点和其所有孩子节点家中能盗取的最大金额。

g(node)表示node节点不被打劫，从其所有孩子节点家中能被盗取的最大金额。

那么：

f(node)=node.val+g(node.left)+g(node.right)

g(node)=max(f(node.left),g(node.left))+max(f(node.right),g(node.right))

那么很明显可以看出，f和g不能是数组了，应该是哈希表map，key是节点，value是对应的金额。

而且node节点对应的value值依赖于其孩子节点，所以应该是从最底层的节点一步一步向上更新的，所以需要使用深度优先搜索dfs（递归）。（相当于用递归对二叉树进行了一次后序遍历。）

代码如下：

var rob = function (root) {
    let fMap=new Map();
    let gMap=new Map();
    
    function dfs(node){
        if(node==null)
            return;
        dfs(node.left);
        dfs(node.right);
        fMap.set(node,node.val+(gMap.get(node.left)||0)+(gMap.get(node.right)||0));
        gMap.set(node,Math.max(gMap.get(node.left)||0,fMap.get(node.left)||0)+Math.max(gMap.get(node.right)||0,fMap.get(node.right)||0));
    }
    dfs(root);
    return Math.max(fMap.get(root)||0,gMap.get(root)||0);
};