As a skilled thief, you are planning to rob multiple houses on a street, each of which contains a substantial amount of money. However, you cannot rob the adjacent houses due to the connected security systems. Otherwise, the police will be contacted automatically.

Given an array of integers, nums, representing the amount of money present in each house, return the maximum amount of money that you can successfully steal without notifying the police.

Constraints

• $1 \leq$ nums.length $\leq 900$
• $0 \leq$ nums[i] $\leq 400$

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

One possible approach would be to use a recursive function that explores all possible paths of robbing the houses. Starting from the first house, we can either rob it or skip it. If we rob the first house, we move on to the third house, since we cannot rob adjacent houses. If we skip the first house, we move on to the second house.

This approach gives us the solution, but it’s computationally expensive, since the time complexity of this algorithm is $O(2^n)$, where $n$ is the number of houses in the street. This is because, in every iteration, we divide the problem into two subproblems. Let’s try to devise a better approach for this problem.

The algorithm discussed above is computationally inefficient because it computes the same subproblem again. For example, assume the following array which contains the money in $5$ houses:

• nums: $[30,50,10,40,20]$

To find the maximum value, we try all possible combinations:

• $30+\textcolor{red}{10+20}=60$

• $30+40=70$

• $30+20=50$

• $50+40=90$

• $50+20=70$

• $\textcolor{red}{10+20}=30$

It can be observed that the combination highlighted in red is computed twice. Computing the same subproblem repeatedly makes the algorithm inefficient. To solve this issue, we use dynamic programming, which stores and uses the results of the subproblems instead of computing them again. We will use the bottom-up approach, also known as the tabulation technique, which is an iterative method of solving dynamic programming problems.

We initialize an array, memo, of a size that is one greater than the length of nums, with zeros. memo stores the amount robbed till a particular house, and we initialize it with zeros because there’s no amount robbed in the beginning. We copy the money from the first house (nums[0]) to memo[1], since it will serve as the maximum theft value in the first iteration. Next, we will iterate nums from the second index and in each iteration i, we choose from the following two options:

• The amount robbed till the previous house so far, given by memo[i].
• The sum of the amount of the current house, given by nums[i], and the amount robbed till the house before the previous one, given by memo[i-1].

To maximize the theft, we take the maximum of these two values and store at memo[i+1]:

memo[i + 1] = max(nums[i] + memo[i - 1], memo[i])

Let’s look at the illustration to get a better understanding of the solution.