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 to fill all values up to , which is your answer.
The implementation follows directly from the recurrence. Each line of code corresponds to part of the mathematical formula. Walk through a small example step by step to verify your understanding.