0
Challenge · 61Dynamic Programming

Spotting overlapping subproblems

DPused in ~95% of apps

Dynamic programming has a reputation for being the hard one, and almost all of that reputation comes from the name. It is recursion that stops answering the same question twice. This lesson is about noticing that it is answering the same question twice, because that is the only genuinely hard part.

Core idea. Write the problem as a recursion first, without worrying about speed. Then look at what it calls. If the same argument comes up in more than one branch, the work doubles at every level and the whole thing is exponential. That repetition is the signal, and remembering answers is the fix.
Playground, this isn't a screenshot
plain recursion, one call at a time
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 15

ways(5) takes 15 calls, and ways(3) is worked out from scratch 2 separate times. That repetition is the whole problem, and it doubles with every step up.

↑ play a little first, then dig in