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.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
filling the table left to right
the table, and the slot being filled
1
01
12
2slot 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