0
Challenge · 63Dynamic Programming
Tabulation: filling a table
DPused in ~95% of apps
The same answers as memoisation, worked out from the bottom instead of the top. No recursion, no stack to overflow, and usually faster. The price is that you have to work out the fill order yourself, and that is the only new idea here.
Core idea. Make an array with one slot per state. Fill it in an order that guarantees every value a slot needs is already sitting there. Then the answer is simply the slot you were asked about, and there is no recursion anywhere.
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