What is Dynamic Programming
Dynamic programming (DP) is a method for solving problems that can be broken into overlapping subproblems. Instead of recomputing the same subproblem multiple times, DP solves each one once and stores the result in a table. The final answer is built up from these stored solutions.
How it works
A problem is a good candidate for DP when it has two properties:
- Optimal substructure — the optimal solution to the problem can be constructed from optimal solutions to its subproblems.
- Overlapping subproblems — the same subproblems appear multiple times during recursion.
The classic example is Fibonacci. The bottom-up DP approach fills an array from the smallest cases upward:
dp[0] = 0
dp[1] = 1
dp[2] = dp[1] + dp[0] = 1
dp[3] = dp[2] + dp[1] = 2
dp[4] = dp[3] + dp[2] = 3
dp[5] = dp[4] + dp[3] = 5
Each entry is computed once, using previously computed entries. No recursion, no repeated work. The time complexity is O(n) and the space is O(n) — or O(1) if you only keep the last two values.
Compare this with memoization, which is the top-down approach: start with the original problem, recurse, and cache results as you go. Both techniques eliminate redundant computation. The bottom-up approach avoids recursion overhead entirely, while memoization only computes subproblems that are actually needed.
DP applies far beyond Fibonacci. Classic DP problems include:
- Shortest paths — Dijkstra's and Bellman-Ford build shortest-path tables from source to all nodes.
- Knapsack — choosing items to maximize value within a weight limit.
- Longest common subsequence — comparing two strings for similarity.
- Edit distance — the minimum number of insertions, deletions, and substitutions to transform one string into another.
The key insight in each case is identifying the subproblem, defining the recurrence relation (how a solution depends on smaller solutions), and choosing the right table dimensions.
Why it matters
Dynamic programming transforms exponential brute-force solutions into polynomial-time algorithms. It is one of the most powerful techniques in algorithm design and appears constantly in interviews, competitive programming, and real systems (routing, text comparison, resource allocation). Learning to spot the subproblem structure is the skill that makes DP accessible.
See How Recursion Works for the progression from recursion to memoization to bottom-up DP.