No Two Adjacent
A row of n houses each hold some amount of money. You may not take from
two houses that are next to each other.
Print the largest total you can take.
This is the shape almost every linear dynamic programming problem has. At each house there are two futures, and the answer is a maximum over them: take this house and add the best from two back, or skip it and keep the best from one back.
The branch that catches people is the take: adding the best from ONE back silently allows two adjacent houses, produces a larger number, and passes every small test.