One-dimensional Dynamic Programming
Take it or skip it
The first real choice. Two options per element, and the constraint decides what taking costs you.
Key idea
The shape
A great many problems reduce to walking a list and deciding, at each element, whether to take it. The constraint is what makes it interesting: taking something usually forbids taking something else.
The recursion is two calls. Take this element, add its value, and continue from wherever the constraint allows. Or skip it and continue from the next one. Return the better of the two.
Below is that comparison at a single position, with the answers from further right assumed already known. Taking an item here forbids the next gap items, so the take branch jumps further than the skip branch.
Why it works
What the state means
Say it precisely: the answer for index i is the best total obtainable considering only elements from i onward. Not the best so far, and not the best including i.
That sentence decides everything else. The base case is zero because there is nothing left. The answer is the value at index 0. And nothing outside the recursion needs to track a running total, because each subproblem's answer is self-contained.
Writing that sentence down before coding is the single highest-value habit in this unit. Most wrong dynamic programming is a correct recurrence over a state that means something slightly different from what the author thought.
Tip
Forward or backward, pick one
The version above indexes from the current position forward. The equivalent table version usually runs the other way, where the answer at i is the best considering elements up to and including i.
Both are correct and their recurrences look different. Mixing them, by writing a forward recursion and then a backward table, is a reliable way to produce something that is nearly right. Choose the direction with the state sentence and keep it.
Key idea
The constraint lives in one number
In the comparison above, gap is the only thing encoding the rule. With a gap of two, taking an element skips the next two. With a gap of one, it skips only the next.
Changing that number changes the problem while leaving the structure untouched, which is worth noticing: this whole family shares one implementation and differs only in where the take branch continues from.
Tip
Choose inputs that can tell the cases apart
On [5, 1, 1, 5] the answer is 10 whether the gap is one or two, because taking both fives is allowed either way. An input like that cannot tell you whether your gap handling is right.
Use one where the gap matters, such as [5, 4, 5]: a gap of one allows both fives for 10, and a gap of two allows only a single 5. Choosing test inputs that can distinguish the cases is part of the work, not a step afterwards.
Cost
Cost
Each index is computed once and does constant work, so O(n) time and O(n) space for the memo, plus O(n) recursion depth.
The table version is the same time with no recursion depth, and the rolling version drops the space to O(1) because the recurrence reaches back a fixed distance. The unmemoized recursion is exponential, roughly 2 to the n, which is worth stating as the thing being fixed.
Predict the output: what the constraint actually forbids
Every selection of non-adjacent positions from four values is listed, with its total. Type the two lines it prints.
House Robber
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.