Mathwords logoMathwords

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

rn=max⁡1≤i≤n(pi+rn−i),r0=0r_n = \max_{1 \le i \le n} \left( p_i + r_{n-i} \right), \qquad r_0 = 0
Where:
  • rnr_n = Maximum revenue from a rod of length n (the subproblem value)
  • pip_i = Price of a single uncut piece of length i
  • ii = Length of the first piece you cut off
  • rn−ir_{n-i} = 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.
r0=0,r1=p1+r0=1r_0 = 0, \qquad r_1 = p_1 + r_0 = 1
Step 2: Build up the table. For each length, try every first cut and reuse the stored answer for the leftover piece.
r2=max⁡(1+1, 5+0)=5,r3=max⁡(1+5, 5+1, 8+0)=8r_2 = \max(1 + 1,\ 5 + 0) = 5, \qquad r_3 = \max(1 + 5,\ 5 + 1,\ 8 + 0) = 8
Step 3: Solve the full problem with the stored values. Each of the four options takes one lookup, with no repeated work.
r4=max⁡(1+8, 5+5, 8+1, 9+0)=10r_4 = \max(1 + 8,\ 5 + 5,\ 8 + 1,\ 9 + 0) = 10
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.

Related Terms