Dynamic Programming

Dynamic programming (DP) turns slow recursive solutions into fast ones by remembering the answers to subproblems instead of recomputing them. It applies whenever a problem has two properties: optimal substructure (the solution is built from solutions to smaller subproblems) and overlapping subproblems (the same subproblems appear over and over).

The Fibonacci Example

Naive recursive fibonacci computes fib(5) by calling fib(4) and fib(3), then fib(4) calls fib(3) again, and so on. The work doubles at every level: O(2^n). With memoization the same call tree solves each subproblem exactly once and reuses the cached answer, dropping the cost to O(n).

Two DP Styles

There are two ways to organize a DP solution:

• Top-down (memoization) — write the recursive solution, then add a cache. Each call checks the cache before recurring. Easy to write because you start from the recursive definition.
• Bottom-up (tabulation) — iterate from the smallest subproblem up to the answer, filling a table. Often slightly faster (no recursion overhead) and easier to optimize for memory.

Both have the same time complexity. Pick whichever is clearer for the problem.

Designing a DP Solution

Three questions get you from problem statement to working DP:

1. What is a subproblem? Phrase it precisely: "the minimum coins needed to make amount i."
2. What is the recurrence? Express the answer for one subproblem in terms of smaller ones.
3. What are the base cases? The smallest inputs that you can answer directly.

For climbing stairs: dp[i] = dp[i-1] + dp[i-2] (you arrive at step i from step i-1 or i-2), with dp[0] = 1.

Common DP Problems

Once you spot the pattern, DP shows up everywhere: longest common subsequence, edit distance (used in spell checkers and diff), the knapsack problem, coin change, matrix chain multiplication. They all share the same template — pick subproblem, recurrence, base case, fill the table.

Try It Yourself

• Solve coin change: minimum coins needed to make amount n from a list of denominations
• Compute the longest common subsequence of two strings
• Optimize the climbing-stairs solution to use O(1) memory instead of O(n)