LeetCode 198: House Robber — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Medium — Dynamic Programming | Array | Optimization

The Problem

Given an array of non-negative integers representing the amount of money in each house, determine the maximum amount you can rob without robbing two adjacent houses.

Approach

Use dynamic programming where dp[i] represents the maximum money that can be robbed up to house i. For each house, choose the maximum between robbing the current house plus the best from two houses back, or keeping the best from the previous house.

Time: O(n) · Space: O(n)

Code

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]

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

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

        return dp[-1]