House Robber | LeetCode 198

AFFILIATE LINKS

Great resource I use to learn algorithms.
40% off Tech Interview Pro: http://techinterviewpro.com/terriblewhiteboard
20% off CoderPro: http://coderpro.com/terriblewhiteboard

We can use dynamic programming to solve this. First, make an array. Each index in the array will represent the choice that will give us the most money up to that point.

The value of index zero is simple. It’s the same as the value of the first house. Think of it this way. If we have only been to one house, we have no decision to make yet. We take what’s in the house.

Then we get to the next house. Do we rob it or do we keep what was in the first house? We make the decision that gets us the most value (the max value of the first and second houses). We can’t choose both because we can’t rob consecutive houses.

Now we apply a different formula for the rest of the indeces in the array. For every index, we choose the greater of a) the sum of our decisions through two houses ago plus the house we’re on or b) the value through the last house. We have to choose one or the other because we have to make sure we don’t rob two houses in a row.

After we’ve made all of these decisions, we return the last index of the array since that represents the sum of our decisions through the final house.

Here is the full implementation.

/**
 * @param {number[]} nums
 * @return {number}
 */
let rob = function(nums) {
    if (nums === null || nums.length === 0) { // if there are no houses, the total is zero
        return 0;
    } else if (nums.length == 1) {
        return nums[0]; // if there is only one house, return its value
    }

    let runningTotal = [];
     /* the first index will be the same value as the first house since there are no decisions to make at this point */
    runningTotal[0] = nums[0],
    /* the second index will be the greater value of the first house or the second house */
    runningTotal[1] = Math.max(nums[0], nums[1]);

    /* start at index 2 since we already have already made our 0th and 1st decisions (which correspond to our first and second houses) */
    for (let i = 2; i < nums.length; i++) {
        /* for each index, we choose the greater of (the current house's value plus the total from two houses ago) or (the total through the last house)  */
        runningTotal[i] = Math.max(nums[i] + runningTotal[i - 2], runningTotal[i - 1]);
    }

    // return the last value in the array. this will be the optimal solution
    return runningTotal[runningTotal.length - 1];
};