Remembering, and take it or leave it

The shortest way to turn a branching recursion into DP is to remember: on the way in, look in a dictionary for "have I solved this before?"; on the way out, write the answer there. The rest of the code stays the same; every repeated branch of the call tree collapses into one lookup.

1def best(i, memo):
2    if i >= len(values):
3        return 0
4    if i not in memo:
5        take = values[i] + best(i + 2, memo)
6        skip = best(i + 1, memo)
7        memo[i] = max(take, skip)
8    return memo[i]

The same solution can be written with a table, back to front or front to back; here two variables are even enough, since only the last two values are needed. Write the remembering recursion first and see that it is right; simplifying comes after.