Solution: House Robber

Statement

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$

Solution

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.

Naive approach

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)$ ...