⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#198) before relying on it.

🏠 House Robber

An interactive visualization of how dynamic programming finds the maximum money you can rob from houses without robbing two adjacent ones. Watch the algorithm make rob vs skip decisions.

Dynamic Programming LeetCode 198 ↗ Medium

The Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses are arranged in a row, and adjacent houses have security systems connected — if you rob two adjacent houses, the alarm will trigger.

Given an integer array nums representing the amount of money at each house, return the maximum amount of money you can rob tonight without alerting the police.

Interactive Visualization

Houses (comma-separated)

Preset

Speed:

Houses

DP Array (Max Money at Each Position)

Status

Press Step or Play to begin.

Code

fun rob(nums: IntArray): Int {    val n = nums.size    if (n == 0) return 0    if (n == 1) return nums[0]    val dp = IntArray(n)    dp[0] = nums[0]    dp[1] = maxOf(nums[0], nums[1])    for (i in 2 until n) {        dp[i] = maxOf(            dp[i-1],           // skip house i            dp[i-2] + nums[i]  // rob house i        )    }    return dp[n-1]}

def rob(nums):    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-1],           # skip house i            dp[i-2] + nums[i]  # rob house i        )    return dp[n-1]

How It Works

Key Insight

At each house i, you have two choices: rob it or skip it. If you rob house i, you get nums[i] money plus the maximum you could have robbed up to house i-2 (since you can't rob adjacent houses). If you skip house i, you keep the maximum money from house i-1. The optimal solution is the better of these two choices.

The Algorithm

Base cases: If there's 0 houses, return 0. If there's 1 house, rob it. If there are 2 houses, rob the one with more money.
Build DP array: For each house i from 2 to n-1, calculate dp[i] as the maximum of:
- dp[i-1]: Skip house i, keep previous max
- dp[i-2] + nums[i]: Rob house i, add to max from two houses back
Return result: dp[n-1] contains the maximum money you can rob.

Recurrence Relation

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Complexity

Time O(n)

Space O(1)

We iterate through the array once, doing constant work at each house. The time complexity is O(n). The space shown here is O(n) for the DP array, but this can be optimized to O(1) by only keeping track of the last two values (dp[i-1] and dp[i-2]).