LeetCode 198 House Robber - Implementation

Here is a simple pseudocode for the DP I just defined:

# 1) Take input
Input: n
Input: a[1.n] # 2) Base cases
dp[0] = 0
dp[1] = a[1] # 3) Fill dp[2.n] using the transition formula
for i from 2 to n: take_i = dp[i - 2] + a[i] skip_i = dp[i - 1] dp[i] = max(skip_i, take_i) # 4) Final answer
print dp[n]

Use the transition formula directly on the array $dp[i] = \max\bigl(dp[i - 1],\ dp[i - 2] + \text{a}[i]\bigr)$ to fill all values up to $dp[n]$, which is your answer.

The implementation follows directly from the recurrence. Each line of code corresponds to part of the mathematical formula.