LeetCode 198 House Robber - Example and Complexity 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: $12$. Rob houses 0, 2, 4 (values 2, 9, 1).

$O(n)$ time, single pass. $O(1)$ space keeping only two previous values.