House Robber

Dynamic Programming
Easy

Approach

Diagrams

Analysis

Time

O(n)

Space

O(n)
class Solution:
    def rob(self, nums):
        numHouses = len(nums)

        if numHouses == 0:
            return 0

        if numHouses <= 2:
            return max(nums)

        return self.getMax(nums)

    def getMax(self, nums):
        numHouses = len(nums)

        dp = [0] * numHouses
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for house in range(2, numHouses):
            dp[house] = max(dp[house - 1], dp[house - 2] + nums[house])

        return dp[-1]

Learn

#Dynamic Programming

Videos