What is Dynamic Programming?
Dynamic programming (DP) solves problems with overlapping subproblems—where the exact same smaller problem is needed many times. Instead of recomputing answers, you solve each subproblem once and store its answer.
Take the naive recursive Fibonacci formula . Plain recursion recalculates twice and three times, causing exponential explosion. Because there are only distinct subproblems, storing them collapses the cost to time.
| Style | Direction | How It Works |
|---|---|---|
| Memoization | Top-down | Natural recursion that caches results on the first call |
| Tabulation | Bottom-up | Fills a table from smallest to largest subproblem |
DP requires two core features: overlapping subproblems and optimal substructure, where an optimal solution builds directly on optimal subproblem solutions.
DP vs. Divide-and-Conquer
Students often confuse dynamic programming with divide-and-conquer. The distinction rests entirely on whether subproblems share work.
| Feature | Divide-and-Conquer | Dynamic Programming |
|---|---|---|
| Subproblems | Independent (e.g., merge sort halves) | Overlapping (reused constantly) |
| Core Goal | Divide and combine | Store and reuse results |
Common pitfall: Applying divide-and-conquer logic to a problem with overlapping subproblems, which triggers catastrophic redundant work.
Classic DP applications include shortest paths, edit distance, the knapsack problem, and longest common subsequence. Each turns an intractable exponential brute-force search into an efficient polynomial-time solution simply by remembering past subresults.