HouseRobberII.java

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

    // rob first house, so need to remove the last house
    int[] rob_first_nums = new int[nums.length - 1];
    for (int i = 0; i < rob_first_nums.length; i++) {
        rob_first_nums[i] = nums[i];
    }

    // do not rob first house, start from the 2nd and rob to the end of the house
    int[] rob_no_first_nums = new int[nums.length - 1];
    for (int i = 1; i < nums.length; i++) {
        rob_no_first_nums[i - 1] = nums[i];
    }

    int rob_first_max = this.robFlatRow(rob_first_nums);
    int rob_no_first_max = this.robFlatRow(rob_no_first_nums);

    return Math.max(rob_first_max, rob_no_first_max);
}

public int robFlatRow(int[] num) {
    if (num == null || num.length == 0) {
        return 0;
    }

    int n = num.length;
    int[] lookup = new int[n + 1]; // DP array size normally larger than 1
    lookup[0] = 0;
    lookup[1] = num[0];

    for (int i = 2; i <= n; i++) {
        lookup[i] = Math.max(lookup[i - 1], lookup[i - 2] + num[i - 1]);
    }

    return lookup[n];
}