vSPARROW

leetcode : 198. House Robber

Posted on June 27, 2020

This is another dynamic programming problem. The way to solve this is to focus only which is greater A) sum of houses robbed until element i or B) the sum of houses robbed up to i-1

The reason we have to make the this decision comes down to the fact that we cannot rob adjacent houses so we have to calculate weather its more profitable to rob the current house or the adjacent houses.

The defaults are the following

• If there are no houses, return 0
• If there is only 1 house return the value of house 1
• If there are 2 houses, return the grater value of house 1 or house 2

after being aware of the above, lets create an array to hold the return value if n were to have equaled i. To rephrase, break the problem size down. Instead of worrying about what happens when the array size is n, lets worry about what would we return if we stopped the array right now.

var rob = function(nums) {
    if(!nums || nums.length === 0){return 0}
    if(nums.length === 1){return nums[0]}
    if(nums.length === 2){return Math.max(nums[0],nums[1])}
    const arr = new Array(nums.length).fill(0)
    arr[0]=nums[0]
    arr[1]=Math.max(nums[0],nums[1])
    for(i=2;i<nums.length;i++){
        arr[i] = Math.max(nums[i] + arr[i-2], arr[i-1])
    })
    return Math.max(arr[arr.length-1],arr[arr.length-2])
};

If you are having a problem understanding, just walk through the first few steps

If nums is 4,2,8,9,0 this is what we would fill our new array with

• [0] -> nums[0] -> 4
• [1] -> the greater of nums[0] or nums[1] -> 4
• [2] -> the greater of nums[2] + array[0] = 12 or array[1] = 2 -> 12
• [3] -> the greater of nums[3] + array[1] = 13 or array[2] = 12 -> 13
• [4] -> the greater of nums[4] + array[2] = 12 or array[3] = 13 -> 13

We return 13