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