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.
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