Dynamic Programming Algorithms

Dynamic Programming Algorithms

Imagine you are climbing a staircase and someone asks, "How many distinct ways can you reach step 10 if you climb 1 or 2 steps at a time?" A naive approach explores every sequence of moves from the bottom. But notice something: the number of ways to reach step 10 is just the ways to reach step 9 (then take one step) plus the ways to reach step 8 (then take two). The answer to a big problem is built entirely out of answers to smaller versions of the same problem — and those smaller answers keep reappearing. Dynamic programming (DP) is the discipline of computing each smaller answer exactly once, storing it, and reusing it. That's the whole idea: trade a little memory to erase mountains of repeated work.

Precise definition

Dynamic programming applies to problems with two structural properties:

• Optimal substructure: an optimal (or total) solution to the problem can be assembled from optimal (or total) solutions to its subproblems. Formally, there is a recurrence expressing f(n) in terms of f at smaller arguments.
• Overlapping subproblems: the same subproblems are solved many times by a naive recursion, so the space of distinct subproblems is small (polynomial), even when the recursion tree is exponential.

When both hold, DP evaluates the recurrence over the distinct subproblems only. Two implementation styles exist. Top-down memoization recurses as usual but caches each result in a table and returns the cached value on re-entry. Bottom-up tabulation orders the subproblems from smallest to largest and fills a table iteratively, no recursion needed. Both give the same asymptotics; the cost of a DP is (number of distinct states) × (work per state to combine children).

Contrast this with divide-and-conquer (subproblems don't overlap, e.g. mergesort) and greedy (a locally optimal choice is provably globally optimal, so you never revisit a state). DP is the tool when subproblems overlap and no greedy choice is safe.

Worked example: Fibonacci, with the operations counted

Define F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). The naive recursion recomputes shared subtrees. Count the addition operations to get F(5) naively: the number of leaf calls equals F(n+1), and the number of additions is F(n+1) - 1. For F(5) that is F(6)-1 = 8-1 = 7 additions, but the call tree has 15 nodes — F(2) alone is recomputed 3 times, F(1) 5 times. In general the naive tree has roughly φn ≈ 1.618n nodes — exponential.

Now memoize. We compute each of F(0)..F(5) once and store it:

• F(2) = F(1)+F(0) = 1+0 = 1
• F(3) = F(2)+F(1) = 1+1 = 2
• F(4) = F(3)+F(2) = 2+1 = 3
• F(5) = F(4)+F(3) = 3+2 = 5

That is exactly 4 additions and 6 stored states versus 15 recursive calls. There are n+1 distinct states, each doing O(1) work: total time drops from exponential to Θ(n). The diagram below shows the collapse from tree to line.

How to design a DP (the reusable recipe)

Interviewers want to see a repeatable method, not a memorized answer:

• Define the state. What are the minimal parameters that fully describe a subproblem? (e.g. dp[i][w] = best value using items 0..i with capacity w.) Getting the state wrong dooms everything else.
• Write the recurrence / transition. Express dp[state] from smaller states, capturing every choice (take item i or skip it → max of the two).
• Establish base cases. The smallest states that are answered directly.
• Choose an evaluation order. Any topological order of the state dependency graph — that's why the graph must be a DAG.
• Read off the answer, and if needed reconstruct the choices by backtracking through the table.

Common pitfalls and what an interviewer probes

• Undercounted state. Leaving out a parameter that the transition actually depends on gives wrong answers that pass small tests. Interviewers push edge cases to expose this.
• Cyclic dependencies. DP requires the state graph to be acyclic; if dp[a] needs dp[b] and vice versa, you need a different tool (shortest paths with negative-cost cycles, etc.). They ask "why is your evaluation order valid?"
• Confusing DP with greedy. A classic trap: coin change with arbitrary denominations. Greedy (always take the largest coin) fails for coins {1,3,4} making 6 — greedy gives 4+1+1 = 3 coins, DP finds 3+3 = 2. Expect a probe on why greedy is unsafe here.
• Memory. A full dp[i][w] table costs O(states) space; many DPs only reference the previous row, so you can compress to O(width). Knowing this rolling-array trick signals maturity.
• Pseudo-polynomial confusion. The 0/1 knapsack runs in O(nW) — polynomial in W's value but exponential in its bit length. Interviewers love asking whether this makes knapsack "efficient." (It doesn't; the problem is NP-hard.)

When it matters in practice + trade-offs

DP is the backbone of sequence alignment (Needleman–Wunsch in bioinformatics), text diffing and edit distance, optimal parenthesization (matrix-chain multiplication), resource allocation (knapsack-style planning), shortest paths (Bellman–Ford, Floyd–Warshall), and the Viterbi algorithm in speech and error-correcting codes. Anywhere you optimize over a sequence of dependent decisions, DP is a first suspect.

The trade-off against neighbouring complexity classes is stark. Naive recursion over overlapping subproblems is exponential (Θ(cn)); DP typically collapses this to polynomial — often Θ(n), Θ(n2), or Θ(nW) — at the cost of proportional memory. Against greedy (usually Θ(n log n) and O(1) extra space), DP is slower and heavier but correct on the many problems where no greedy choice is provably optimal. And DP does not defeat NP-hardness: for problems like knapsack or TSP, the state space itself is exponential in the input size (TSP's held-Karp DP is O(n22n)), so DP merely gives the best-known exact bound, not a polynomial one. The judgment call: reach for DP when subproblems overlap and greedy is unsafe; reach for greedy when a exchange-argument proves the local choice; and accept exponential DP only when exact answers on small n justify it.

Key takeaways

• DP applies exactly when a problem has optimal substructure (a recurrence) and overlapping subproblems (few distinct states); it computes each state once and reuses it.
• Total cost is (#distinct states) × (work per transition) — this single formula predicts nearly every DP's runtime and turns exponential recursion into polynomial time.
• The design recipe is fixed: define the state, write the transition, set base cases, pick an acyclic evaluation order, then read off and optionally reconstruct the answer.
• DP beats naive recursion and outperforms greedy on problems where greedy is unsafe, but it does not break NP-hardness — for knapsack/TSP the state space is itself exponential.