Leetcode - House Robber (with JavaScript)

Today I am going to show how to solve the House Robber algorithm problem.

Here is the problem:

For solving this problem, I’ll use dynamic programming to keep an array of the maximum amounts of money that we can rob, as I loop through an array of houses.

Before doing all of that, I write the first case of when there is no house to rob:

var rob = function(nums) {

    if( nums == null || nums.length == 0) {
        return 0
    }

};

Now I make a dynamic programming array and start looking at the houses one by one.

The maximum amount of money we can rob up to the 1st house(nums[0]) is just for robbing that house.
The maximum amount of money we can rob up to the 2nd house (nums[1]) would be either the maximum of the 1st (nums[0]) or of the 2nd (nums[1]) house, whichever is greater.

var rob = function(nums) {

    if( nums == null || nums.length == 0) {
        return 0
    }

    dp = []
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])

};

At the 3rd (nums[2]) house, everything gets more interesting. Because we can not rob adjacent houses, we have to decide between robbing both the 3rd and the 1st house, or just robbing the 2nd house.

Because we’ve already checked the first 2 houses, I will start looping at the third house, where i=2.

The loop will check which is greater: robbing the current house + the maximum amount of money we can get from the 2 houses before it, or the previous maximum amount of money we robbed.

At the end, all we have to do is just return the last element of the dp array.

var rob = function(nums) {

    if( nums == null || nums.length == 0) {
        return 0
    }

    dp = []
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])

    for (let i = 2; i < nums.length; i++){
        dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2])
    }

    return dp[nums.length - 1]

};