[2018-Interview] House Robber

Original question: https://leetcode.com/problems/house-robber/description/

My answer: The key point here is that we set up a new array, robbedMaxMoney, where the "i"th element in robbedMaxMoney indicated the max Money with "i"th house must be robbed. Thus, robbedMaxMoney[i] = max(robbedMaxMoney[i - 3], robbedMaxMoney[i - 2]) + nums[i];

The above equation means that the "i" the element must be the biggest value among "i - 3" and "i - 2" plus nums[i], because "i - 1" cannot be an option. Meanwhile, [i - 4] element can add both nums[i -2] and nums[i], so we don't need to worry about [i-4], aka no need to get the biggest value among "i - 4", "i - 3" and "i - 2", as robbedMaxMoney[i-4] must be already considered in robbedMaxMoney[i-2].

Finally, the end result should be the bigger of the last 2 elementss of robbedMaxMoney , aka robbedMaxMoney[end] and robbedMaxMoney[end - 1]

class Solution {
    public int rob(int[] nums) {
        int maxMoney = 0;
        if (nums == null || nums.length == 0) {
            return maxMoney;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int[] robbedMaxMoney = new int[nums.length];
        // the "i"th element in robbedMaxMoney indicated the max Money

        // can be robbed with "i"th house must be robbed
        robbedMaxMoney[0] = nums[0];
        robbedMaxMoney[1] = nums[1];
        if (nums.length == 2) {
            return Math.max(robbedMaxMoney[0], robbedMaxMoney[1]);
        }
        robbedMaxMoney[2] = nums[0] + nums[2];
        for (int i = 3; i < nums.length; i ++) {
            robbedMaxMoney[i] = Math.max(robbedMaxMoney[i - 2], 

                                         robbedMaxMoney[i - 3]) + nums[i];
        }
        return Math.max(robbedMaxMoney[nums.length - 2],

                        robbedMaxMoney[nums.length - 1]);
    }
}