AlgoScope

House Robber

best(i) = max(best(i-1), best(i-2) + value(i)). Take or skip.

Dynamic programming, algorithm, intermediate
House 1: the best total so far is 7.2071923314i
House 1: the best total so far is 7.2071923314i

DP in One Row: House robber

Decision, step 3 of 7

House 1 is worth 7. Skip it: dp[0] = 2. Take it: dp[-1] + 7 = 7. Best: 7, take.

How dp in one row works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Taught by the same lesson

DP in One Row covers these too, in the same run.