LeetCode Daily Challenge: House Robber solution using dynamic programming
Tags: leetcode, python, algorithms, programming
Published: 2022-12-16 13:00:25

## Introduction

This is an article to discuss a LeetCode challenge solution.
If you want to see the full challenge description with examples click on the following link:
[198. House Robber](https://leetcode.com/problems/house-robber/description/)

## The problem

> "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 of each house, return the maximum amount of money you can rob tonight without alerting the police."

## Using dynamic programming over recursion

I first solved this problem using a recursive function. However when submitting the solution there was a time limit exceeded for longer inputs. So I had to optimize my solution using dynamic programming. My recursive solution looks like this:

```Python
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        return max(nums[0] + self.rob(nums[2:]), self.rob(nums[1:]))
```
The solution above consists on checking and treating the base cases (when there is no houses to rob or when there's only one house in the list) and, if the list includes more than one house, we get the max amount between including the first house and not doing it.

When using dynamic programming to optimize the solution above, the logic behind it consists of creating a table which we can store the max amount for each position from start to the `Nth` position (we're gonna call this variable `moneyBag`). So we iterate over the input list and for each iteration we calculate the max amount the robber can get from the first position until that current position. To do that we need to consider the max amount from start to two houses (positions) before the current position, and the max amount from start to the previous position. To calculate the max amount for the current position we get the max between _the max from two positions before plus the current value_ and _the max from the previous position_.
The max possible amount the robber can get will be last element of the `moneyBag`.

```Python
class Solution:
    def rob(self, nums: List[int]) -> int:
        moneyBag = [0, 0]
        for num in nums:
            moneyBag.append(max(num + moneyBag[-2], moneyBag[-1]))
        
        return moneyBag[-1]
```

If you want to optimize even more this solution you can replace the `moneyBag` list with two variables (here we're gonna call them `bag1` and `bag2`) once we're only using the two previous positions in each iteration.

```Python
class Solution:
    def rob(self, nums: List[int]) -> int:
        bag1 = 0
        bag2 = 0
        for i, num in enumerate(nums):
            currentBag = max(num + bag1, bag2)
            bag1 = bag2
            bag2 = currentBag
        
        return bag2
```

The runtime complexity for this last solution is O(n) and the space complexity is O(1) which makes it the optimal solution.