House Robber

Medium Subject: 1-D Dynamic Programming

Time Complexity

O(N)

Space Complexity

O(1)

Problem Description

Problem Statement

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

Example 1:

Input: nums = [1,2,3,1]
Output: 4

Optimal Solution

Python

Approach: Bottom-Up DP

We maintain two variables: rob1 (max money if we rob up to house i-2) and rob2 (max money up to house i-1). For house i, the max is max(rob1 + nums[i], rob2).

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0

        for n in nums:
            temp = max(n + rob1, rob2)
            rob1 = rob2
            rob2 = temp

        return rob2