House Robber

This is a series problems: House Robber and House Robber II.

The former problem is a simplest Dynamic Programming problem. At index i, the maximum rob earning value comes from i - 2 and i - 3. Houses numbered below i - 3 has no effect on i as each of them can either jumps to i - 2 or i - 3 to get a higher learning. So the DP iterating formular is:

$$DP[i] = \max \{DP[i - 2], DP[i - 3]\} + nums[i]$$

We finally return the max value among all $DP[i]$.

Sample code:

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

        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        int max = dp[0];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = nums[i];
            // Do not need to check k < i - 3. 
            for (int j = 2; i - j >= 0 && j <= 3; j++) {
                dp[i] = Math.max(dp[i], dp[i - j] + nums[i]);
            }
            max = Math.max(dp[i], max);
        }

        return max;
    }
}

In the second problem, the houses are arranged in a circle. The simplest way to solve this problem is cut the circle at the position between n - 1 and 0 and reuse the method used in the first problem. We need to apply the method twice, one with the first house robbed and one without. Then we pick the maximum income between two cases.

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

        int[] withone = new int[nums.length - 1];
        withone[0] = nums[0];

        int max = nums[0]; // Use nums[0] instead of 0 !

        for (int i = 1; i < withone.length; i++) {
            int l = (i - 2 >= 0) ? withone[i - 2] : 0;
            int ll = (i - 3 >= 0) ? withone[i - 3] : 0;
            withone[i] = Math.max(l, ll) + nums[i];
            max = Math.max(max, withone[i]);
        }

        int[] withoutone = new int[nums.length];

        for (int i = 1; i < withoutone.length; i++) {
            int l = (i - 2 >= 0) ? withoutone[i - 2] : 0;
            int ll = (i - 3 >= 0) ? withoutone[i - 3] : 0;
            withoutone[i] = Math.max(l, ll) + nums[i];
            max = Math.max(max, withoutone[i]);
        }
        return max;
    }
}