##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Walkthrough and analysis
Trace nums = [2,7,9,3,1].
dp[0] = 2 (rob house 0) dp[1] = max(2, 7) = 7 (better to rob house 1) dp[2] = max(dp[1], dp[0] + 9) = max(7, 2+9) = 11 dp[3] = max(dp[2], dp[1] + 3) = max(11, 7+3) = 11 dp[4] = max(dp[3], dp[2] + 1) = max(11, 11+1) = 12
Answer: . Rob houses 0, 2, 4 (values 2, 9, 1).
time, single pass. space keeping only two previous values.
