Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Problem

House Robber

LeetCode #198Medium

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

Houses are arranged in a row, each holding some money, but robbing two adjacent houses triggers the alarm. Return the maximum amount you can rob without alerting the police.

Asked atAmazonGoogleLinkedIn

Brute force · recursion

time O(2ⁿ)space O(n)

step 1 / 10

[0][1][2][3][4]

Brute force · recursion


▸
1rob(i):
2    if i < 0: return 0
3    return max(rob(i−1), rob(i−2) + nums[i])   // recomputes!

state

nums[2, 7, 9, 3, 1]
recurrencerob(i) = max(rob(i−1), rob(i−2) + nums[i])

line 1House Robber: houses sit in a row, each holding some cash, but the alarm trips if you rob two ADJACENT houses. Standing at house i you face one binary choice — rob it or skip it. If you skip, the best you can do is whatever was best up to house i−1. If you rob it, you collect nums[i] but must have stopped at i−2 (i−1 is now off-limits). So rob(i) = max(rob(i−1), rob(i−2) + nums[i]).