House Robber Leetcode Solution

Hello and welcome back to the Leetcody Daily Series!

Today, we're going to solve yet another dynamic programming problem, but thankfully, this one is much simpler than yesterday! So, without further ado, let's dive in!

Understanding the Problem

Give the following problem description a few reads:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money for each house, return the maximum amount of money you can rob tonight without alerting the police.

If this seems a bit confusing to you, try to solve this problem mentally for the given example:

nums = [2,7,9,3,1]

If you got the answer as 12, you've started to grasp the essence of the problem.

Now, let's think about what method we could use to solve this problem.

Intuition

If you have read the Minimum Falling Path Sum article, you would remember the two foremost clues to look for in a dynamic programming problem. If not, please go ahead and give that a look.

Now, observe this problem carefully. Does it provide the two clues that almost all dynamic programming problems have?

First, what quantity do we need to compute? The maximum amount of money the thief can steal.

Second, do we have a choice of which elements to pick? The given constraint specifies that we can only choose non-adjacent elements from the array to maximize the sum.

Quite clearly, this problem will be solved by dynamic programming.

Coding Up The Steps

To solve this problem, we need an array of size equal to the input array, let's call it dp.

Now, the ith element of this array will store the maximum possible amount of money the thief can steal up to the ith index. So, we initialize the first element of dp with the first element of the input array.

The second element of dp will have the value of the maximum of the first two elements of the input array. Can you guess why?

If the input array was of size 2, the answer would obviously be the maximum of those two elements, right?

For the elements that follow, we use the following code:

    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);

        for(int i = 2; i < n; i++){
            dp[i] = max(dp[i-1],dp[i-2] + nums[i]);
        }
        return dp[n-1];
    }

The essence of the entire problem is in this one line:

dp[i] = max(dp[i-1] , dp[i-2] + nums[i]);

This line represents the two choices we have for every element. Say we're at index i, should we include this element or not?

If we do include this element, what will be the corresponding value in the dp array? It will be dp[i-2] + nums[i] since if we include the ithelement, we can't include the (i-1)th element in our answer. So we take the answer up till the (i-2)th index and add the current index's value to it.

If we don't include the current element, then the value of dp[i] will be the same as dp[i-1] . Since we need to find the maximum amount the thief can steal, we choose the maximum value from these two choices and assign it to dp[i] .

The final answer will be stored in the last element of dp.

That's it for this problem! If you enjoyed this post, please leave a like and feel free to leave any suggestions in the comments. See you tomorrow for yet another leetcode solution!

Cheers!