Dynamic Programming
Think of it like this
You're climbing stairs and can take 1 or 2 steps at a time. How many ways to reach step 5?
The naive way: draw the full recursion tree.
ways(5) = ways(4) + ways(3)
ways(4) = ways(3) + ways(2) ← ways(3) computed TWICE
ways(3) = ways(2) + ways(1) ← ways(2) computed THREE times
ways(2) = ways(1) + ways(0) = 2
ways(1) = 1
ways(0) = 1The tree grows exponentially. But notice, ways(3) is computed twice and always gives the same answer. If you cache it the first time, you never recompute it.
That's the entire idea behind DP: cache the results of overlapping subproblems.
Two Requirements for DP
A problem is solvable by DP only if it has:
- : The same subproblem appears multiple times in the recursion tree