DEV Community

Urfan Guliyev
Urfan Guliyev

Posted on

Leetcode - House Robber (with JavaScript)

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

Here is the problem:
Alt Text

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
    }

};
Enter fullscreen mode Exit fullscreen mode

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])

};
Enter fullscreen mode Exit fullscreen mode

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]

};

Enter fullscreen mode Exit fullscreen mode

Top comments (0)