Leetcode diary: 198. House Robber

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

HUZZAH!!!!!!! Today started out well with easily solving this DP problem the DP way straight up!!!!!!

For those who struggles with DP problems like this one, I recommend reading through my agonizing pain.

the first thing I did was determine whether we can solve this problem via some kind of progression with incremental sub-problems. Let's say given [1,2,3,1]:
[1]: rob 1
[1,2]: rob 2
[1,2,3]: rob 1 and 3
[1,2,3,1]: rob 1 and 3
As we can see that it is possible to solve it via progression, so we can for loop on the array and get some kind of O(N) solution.

The second thing is to understand what are our choices:
1.) rob house 1 and house 3
2.) rob house 2
These two are our only choices, but at house 1 we don't have 3 houses to choose from.
This is when we need a bit of ingenuity to prepend two 0s at the beginning at start at index 2 instead. This way we can approach the problem as
1.) rob house at index i and i-2
2.) rob house at index i-1

the code is as below:

var rob = function(nums) {    
    const memo = [0,0,nums[0]]; 

    nums.forEach(function(_, index){
        const memoIndex = index+2;
        memo[memoIndex] = Math.max(
            memo[memoIndex-2] + nums[index],
            memo[memoIndex-1]
        );
    })

    return memo[memo.length-1];
};

Now the question we should answer is why does the memoization work.
let's say for [a,b,c,d]
d >>> a >> b > c
in other words at the end of the algorithm we'd expect a+d to be the answer, since:
(a+d) > (b+d) > (a+c)
the memo[] looks like:
[a, a, a+c, a+d]
at the fourth index, what we are really choosing is really
(a+c) vs (a+d), which in English can be rephrased as
"the biggest value before i-1 + nums[i-1]" vs "the biggest value before i-1 + nums[i]".
note that in consideration of just the about statement, "a" does not have to be an element in nums, it can be a summation of numbers travelled thus far in nums.

So what we are really choosing at each step is "the maximal value plus i or maximal plus i-1", since those are the only possible choices given the question constraints, an incremental subproblem approach is appropriate to find the solution.

Let me know anything on your mind after reading through this, THANKS!