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