Dynamic Programming — Definition, Formula & Example
Dynamic programming is a problem-solving method that breaks a big problem into smaller subproblems, solves each subproblem once, and stores its answer so it can be reused instead of recomputed.
Dynamic programming applies to problems with two properties. Optimal substructure means an optimal solution is built from optimal solutions to subproblems. Overlapping subproblems means the same subproblems recur. You define a recurrence (often called a Bellman equation) for the optimal value of each subproblem and evaluate it either top-down with memoization or bottom-up by filling a table. The running time is the total work over all distinct subproblems, often the number of subproblems times the work for each.
Key Formula
Where:
- = Maximum revenue from a rod of length n (the subproblem value)
- = Price of a single uncut piece of length i
- = Length of the first piece you cut off
- = Best revenue from the leftover rod, already stored in the table
Worked Example
Problem: A 4-foot metal rod can be cut into whole-foot pieces. A 1-foot piece sells for $1, a 2-foot piece for $5, a 3-foot piece for $8, and a 4-foot piece for $9. What is the maximum revenue?
Step 1: Start with the smallest subproblems. A rod of length 0 earns nothing, and a 1-foot rod can only be sold whole.
Step 2: Build up the table. For each length, try every first cut and reuse the stored answer for the leftover piece.
Step 3: Solve the full problem with the stored values. Each of the four options takes one lookup, with no repeated work.
Answer: The maximum revenue is $10. You get it by cutting the rod into two 2-foot pieces, which beats selling it whole for $9.
Why It Matters
Dynamic programming is a core topic in college algorithms courses and in technical job interviews for software engineering roles. It powers DNA sequence alignment in bioinformatics, spell-checkers that measure edit distance, and route planning in shortest-path algorithms such as Bellman-Ford and Floyd-Warshall.
Common Mistakes
Mistake: Writing the recurrence as plain recursion without storing results.
Correction: Without a table or memo, the rod-cutting recursion recomputes the same shorter rods again and again, and the number of calls roughly doubles with each extra foot of rod. Store each subproblem's answer the first time you compute it. Then every later use is a single lookup, and the total work grows only polynomially in the rod length.
