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]

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment