House Robber

• 1-dimentional array: Q198.
• Circular array: Q213.
• Binary tree: Q337.

---

House Robber

class Solution {
    public int rob(int[] nums) {
        // max amount of money can be robbed from i to the end
        int[] memo = new int[nums.length];
        Arrays.fill(memo, -1);

        return dp(0, nums, memo);
    }

    private int dp(int index, int[] nums, int[] memo) {
        if (index >= nums.length)
            return 0;
        if (memo[index] != -1)
            return memo[index];

        memo[index] = Math.max(
                nums[index] + dp(index + 2, nums, memo),
                dp(index + 1, nums, memo)
        );

        return memo[index];
    }
}

House Robber II

class Solution {
    public int rob(int[] nums) {
        // max amount of money can be robbed from i to j, including i, j, i > 0
        Integer[][] memo = new Integer[nums.length][nums.length];

        return Math.max(dp(1, nums.length - 1, nums, memo), dp(2, nums.length - 2, nums, memo) + nums[0]);
    }

    private int dp(int from, int to, int[] nums, Integer[][] memo) {
        if (from > to || from >= nums.length)
            return 0;
        if (memo[from][to] != null)
            return memo[from][to];

        memo[from][to] = Math.max(
            dp(from + 2, to, nums, memo) + nums[from],
            dp(from + 1, to, nums, memo)
        );

        return memo[from][to];
    }
}

House Robber III

class Solution {
    public int rob(TreeNode root) {
        Map<TreeNode, Integer> memo = new HashMap<>();

        return dp(root, memo);
    }

    private int dp(TreeNode root, Map<TreeNode, Integer> memo) {
        if (root == null)
            return 0;

        if (memo.containsKey(root))
            return memo.get(root);

        int max = Integer.MIN_VALUE, sum = 0;
        // rob root
        sum = root.val;
        if (root.left != null)
            sum += dp(root.left.left, memo) + dp(root.left.right, memo);
        if (root.right != null)
            sum += dp(root.right.left, memo) + dp(root.right.right, memo);
        max = Math.max(max, sum);
        // not rob root
        sum = dp(root.left, memo) + dp(root.right, memo);
        max = Math.max(max, sum);

        memo.put(root, max);

        return max;
    }
}

• We don't actually go through the same branch twice, therefore it's not necessary to use the memo table. This question can be transfer to a normal recursion - the simplest DP.

class Solution {
    int rob(TreeNode root) {
        int[] res = dp(root);
        return Math.max(res[0], res[1]);
    }

    // 返回一个大小为 2 的数组 arr
    // arr[0] 表示不抢 root 的话，得到的最大钱数
    // arr[1] 表示抢 root 的话，得到的最大钱数
    int[] dp(TreeNode root) {
        if (root == null)
            return new int[]{0, 0};
        int[] left = dp(root.left);
        int[] right = dp(root.right);
        // 抢，下家就不能抢了
        int rob = root.val + left[0] + right[0];
        // 不抢，下家可抢可不抢，取决于收益大小
        int not_rob = Math.max(left[0], left[1])
                    + Math.max(right[0], right[1]);

        return new int[]{not_rob, rob};
    }
}

House Robber IV

• DP or DFS costs $O(nk)$, the worst case would be $O(n^2)$
• we can solve this question by binary search (guessing answer category). Assuming the range of nums[i] is m, the time complexity is $O(nlogm)$.

class Solution {
    public int minCapability(int[] nums, int k) {
        int minCap = Integer.MAX_VALUE;
        int left = nums[0];
        int right = nums[0];
        for (int n : nums) {
            left = Math.min(left, n);
            right = Math.max(right, n);
        }

        // [l, r]
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isValidCap(mid, nums, k)) {
                minCap = mid;
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        return minCap;
    }

    private boolean isValidCap(int cap, int[] nums, int k) {
        int count = 0;
        // greedy
        for (int i = 0; i < nums.length; i++) {
            if (cap >= nums[i]) {
                count++;
                i++;
            }
        }

        return count >= k;
    }
}

// !!! time limit exceeded
class Solution {
int minCap = Integer.MAX_VALUE;

    public int minCapability(int[] nums, int k) {
        dfs(0, nums, k, 0);

        return minCap;
    }

    private void dfs(int index, int[] nums, int k, int cap) {
        // counldn't finish the rob job based on the condition
        if ((nums.length - index + 1) / 2 < k || (k != 0 && index == nums.length))
            return;
        if (k == 0) {
            minCap = Math.min(cap, minCap);
            return;
        }

        // not rob current house
        dfs(index + 1, nums, k, cap);
        // rob current house
        dfs(index + 2, nums, k - 1, Math.max(nums[index], cap));
    }

}

House Robber V

class Solution {
    public long rob(int[] nums, int[] colors) {
        long[] memo = new long[nums.length];

        return dp(0, nums, colors, memo);
    }

    private long dp(int index, int[] nums, int[] colors, long[] memo) {
        if (index >= nums.length)
            return 0;
        if (memo[index] != 0)
            return memo[index];

        long result = 0;
        // not rob current
        long notRob = dp(index + 1, nums, colors, memo);
        // rob current
        long rob = (index < nums.length - 1 && colors[index] != colors[index + 1]) ?
                dp(index + 1, nums, colors, memo) + nums[index] :
                dp(index + 2, nums, colors, memo) + nums[index];
        result = Math.max(rob, notRob);
        memo[index] = result;

        return memo[index];
    }
}