Leetcode 198

最初的就是考虑一维的dp，代码实现如下

class Solution {

 public static int rob(int[] nums) {
        if(nums==null||nums.length==0) return 0;
        if(nums.length<=2) return nums.length==1?nums[0]:Math.max(nums[0],nums[1]);
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[1],nums[0]);
        for(int i=2;i<nums.length;i++)
        {
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }
}

leetcode 213 围成一圈的打家劫舍

对于这种情况就需要比较三种情况的大小，但是第一种情况是不需要比较的，因为情况2和情况3都包括了第一种情况，因为，如果不包括两端，但是仍是最大的话，情况2和情况3都是涵盖

class Solution {

    public int rob(int[] nums)
    {
        if(nums==null||nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        if(nums.length==2) return Math.max(nums[0],nums[1]);
        if(nums.length==3) return Math.max(nums[0],Math.max(nums[1],nums[2]));
        int res=rob1(nums,0,nums.length-2);
        int res2=rob1(nums,1,nums.length-1);
        return Math.max(res,res2);
    }

    public int rob1(int[] nums,int start,int end)
    {
        int[] dp=new int[nums.length];
        dp[start]=nums[start];
        dp[start+1]=Math.max(nums[start],nums[start+1]);
        for(int i=start+2;i<=end;i++)
        {
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[end];
    }
}

二叉树的打家劫舍

对于递归的方法就是脱离了上面两种动态规划的规则

暴力

 public int rob(TreeNode root)
    {
        if(root==null) return 0;
        int money=root.val;
        int money2=0;
        if(root.left!=null)
        {
            money+=rob(root.left.left)+rob(root.left.right);
            money2+=rob(root.left);
        }
        if(root.right!=null)
        {
            money+=rob(root.right.left)+rob(root.right.right);
            money2+=rob(root.right);
        }
        return Math.max(money,money2);
        return robWithMemory(root,new HashMap<TreeNode,Integer>());
    }

带记忆的递归

public int robWithMemory(TreeNode root,HashMap<TreeNode,Integer> map)
    {
        if(root==null) return 0;
        if(map.containsKey(root)) return map.get(root);
        int money=root.val;
        int money2=0;
        if(root.left!=null)
        {
            money+=robWithMemory(root.left.left,map)+robWithMemory(root.left.right,map);
            money2+=robWithMemory(root.left,map);
        }
        if(root.right!=null)
        {
            money+=robWithMemory(root.right.left,map)+robWithMemory(root.right.right,map);
            money2+=robWithMemory(root.right,map);
        }
        int curRes=Math.max(money,money2);
        map.put(root,curRes);
        return Math.max(money,money2);
    }

需要注意的点，就是设置map和取map的两个位置，我本来想着在robWithMemory(root.left.left,map)的这些位置都加上取map的操作，后来看到解析，直接
if(map.containsKey(root)) return map.get(root);即可，这儿是需要注意的

时间最快的递归方式

和二叉树有关的，我们就可以想到二叉树的遍历。
当前这道题其实已经和前面两道题都已经脱离开了，对于这一道题来说，我们可以考虑当前位置要不要偷两种情况。
这一道题可以考虑改写二叉树的后序遍历

public static int rob3(TreeNode root)
    {
        if(root==null) return 0;
        int[] f = f(root);
        return Math.max(f[0],f[1]);
    }
    public static int[] f(TreeNode root)
    {
        if(root==null) return new int[]{0,0};
        //res[0]当前位置不偷
        //res[1]当前位置要偷
        int[] res=new int[2];
        int[] left = f(root.left);
        int[] right=f(root.right);

        res[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        res[1]=root.val+left[0]+right[0];
        return res;
    }

每一个节点，都对应这个两个结果，就是偷和不偷，而且上面的节点是依赖于下面的节点的，所以考虑使用后续遍历，得到左右孩子的结果，然后再来处理当前的