House Robber 1

https://leetcode.com/problems/house-robber/
給定一個int數(shù)組（正整數(shù)）代表每一戶人家的黃金家厌，一個robber泻拦，從第一家開始打家劫舍签舞，不能打劫相鄰的家庭，即打劫了第一家凛剥，下一個智能打劫第三家盆赤。求這個robber最多能打劫多少黃金
Example 1:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

解題思路

DP大法从隆，dp[i] 代表在i的位置上能搶到的最大金額。所以果复，i的狀態(tài)轉(zhuǎn)移方程陈莽，是依賴于i-1和i-2的。 對于i的位置虽抄，可以搶走搁，也可以不搶

• 如果搶了i，那么dp[i] = dp[i-2] + nums[i]
• 如果不搶i迈窟，那么一定搶過i-1 所以dp[i] = dp[i-1]

所以dp[i] = max(dp[i-2] + nums[i],dp[i-1]);

public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

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

House Robber 2

https://leetcode.com/problems/house-robber-ii/
題目1的變種私植，數(shù)組的收尾是相連的，也就是說第一家和最后一家车酣，只能搶其中一家

解析

既然第一家和最后一家只能搶一個曲稼，那就分開算~

• 先剔除最后一家，算(0~lenth-1)的index范圍內(nèi)的最大值
• 剔除第一家湖员，算（1~length）的index范圍內(nèi)的最大值
• 留上面兩個步驟的最大值為最終結(jié)果

    public int rob2(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(rob(nums, 0, nums.length - 1), rob(nums, 1, nums.length));
    }

    public int rob(int[] nums, int left, int right) {
        if (right - left <= 1) {
            return nums[left];
        }
        int size = nums.length;
        int[] dp = new int[size];

        dp[left] = nums[left];
        dp[left + 1] = Math.max(nums[left], nums[left + 1]);

        for (int i = left + 2; i < right; i++) {
            dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
        }
        return dp[right - 1];
    }

HouseRobber 3

https://leetcode.com/problems/house-robber-iii/
還是搶劫問題贫悄，把原來的int數(shù)組變成了一個二叉樹，相鄰的節(jié)點不能同時被搶劫

解析

• 很明確娘摔，這個是需要遞歸來算的~
• 對于二叉樹root來說窄坦，他的最大值，就是 max（func（root）,func(root.left) + func(root.right)）
• 那么func(root)怎么算凳寺，root的值不能與它相鄰的節(jié)點有牽連鸭津，所以只有root.left.right,root.left.left,root.right.left,root.right.right，只有這四個節(jié)點是與它相關(guān)的
  來~ 上代碼

public int rob3(TreeNode root) {
        HashMap<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
        return rob3DFS(root, map);
    }

    public int rob3DFS(TreeNode root, HashMap<TreeNode, Integer> hash) {
        if (root == null) {
            return 0;
        }

        if (hash.containsKey(root)) {
            return hash.get(root);
        }

        int val = 0;

        //如果root有左子樹肠缨，就找左子樹的最大val逆趋，左子樹是和自己挨著的，所以要從左子樹的兩個子節(jié)點下手
        if (root.left != null) {
            val += rob3DFS(root.left.left, hash) + rob3DFS(root.left.right, hash);
        }

        if (root.right != null) {
            val += rob3DFS(root.right.left, hash) + rob3DFS(root.right.right, hash);
        }

        //root的最大值的求法怜瞒，就是以root為根的最大值 對于  left的最大值+ right的最大值（因為left和right不挨著）
        val = Math.max(val + root.val, rob3DFS(root.left, hash) + rob3DFS(root.right, hash));
        hash.put(root, val);
        return val;
    }