LeetCode Daily Challenge: House Robber solution using dynamic programming

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

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:

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.

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.

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.