0
Challenge · 62Dynamic Programming
Memoisation: recursion plus a cache
DPused in ~100% of apps
The smallest possible fix for the biggest possible speed-up. Keep the recursion you already wrote, add three lines, and forty billion calls become fifty one. This is the version to write first in an interview, every time.
Core idea. Before doing the work, check whether this exact question has been answered before. If it has, return the stored answer. If it has not, work it out and store it before returning. Three lines around a recursion you already trust.
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
the same recursion, with a cache
calls so far, indented by depth
ways(5)
times actually worked out
ways(5): 1
ways(4): 0
ways(3): 0
ways(2): 0
ways(1): 0
ways(0): 0
calls made
1
working out ways(5)
step 1 of 9
The same recursion with a cache takes 9 calls instead of 15, and every subproblem is worked out exactly once. Nothing else changed.
↑ play a little first, then dig in