MediumDynamic Programming

House Robber

nums[i] is the money in house i on a street. You can't rob two neighbouring houses. Return the most money you can rob.

nums = [1,1,3,3] → 4nums = [2,9,8,3,6] → 16

Try:
CALL
1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Variables

The data structures the code is building

The street

Money in each house; the number below it is filled in as it is computed

Time and space complexity

n = len(nums). The highlighted row is the solution being traced.

Keyboard: ← → step, Space play or pause. 1 or more amounts from 0 to 100; drawings use at most 6 houses for plain recursion, 10 for top-down and 12 for the loops.