0
Challenge · 64Dynamic Programming

One-dimensional DP

DPused in ~95% of apps

The shape most DP interview questions actually have. Walk along a line making one decision per position, where the decision is limited by what you decided just before. Take it or skip it, and carry two numbers forward.

Core idea. At each position there is a small set of choices, and the best answer for the whole line is built from the best answers for its prefixes. Once you see that only the last one or two positions matter, the table collapses to a couple of variables.
Playground, this isn't a screenshot
filling the table left to right
the table, and the slot being filled
1
0
1
1
2
2
slot 2 reads slots 1 and 0, both already filled, and stores 2. No recursion and no cache, just the right order.
step 1 of 7

The same numbers as the recursion, filled in an order that guarantees what you need is already there. No stack, no cache.

↑ play a little first, then dig in