Dynamic Programming — theory and understanding

Dynamic programming (DP) is a technique for solving a problem by breaking it into smaller subproblems, solving each subproblem once, and reusing the stored answer instead of recomputing it.

The one-sentence definition worth memorising:

DP = recursion + remembering the answers to subproblems you've already solved.

That's it. If you can write a correct recursive solution and the recursion keeps solving the same subproblems over and over, DP turns that exponential recursion into something fast — usually polynomial — just by caching.

The name is historical and misleading: it has nothing to do with "dynamic" memory or programming a computer. Richard Bellman coined it in the 1950s partly because it sounded impressive. Don't let the name intimidate you — think "smart recursion with a memory."

Why it matters in contests: an enormous fraction of medium-difficulty problems are DP. Counting problems ("in how many ways…"), optimisation problems ("maximum/minimum…"), and feasibility problems ("is it possible to…") are very often DP once you spot the right state.

A problem is solvable by DP when it has both of these properties:

1. Optimal substructure — the optimal answer to the whole problem can be built from optimal answers to its subproblems.

Example: the shortest path from A to C through B uses the shortest path from A to B and the shortest path from B to C. The big answer is composed of smaller optimal answers.

2. Overlapping subproblems — the recursion solves the same subproblem multiple times.

Example: naïve fib(n) computes fib(n-2) twice, fib(n-3) three times, and so on — the same calls recur all over the recursion tree.

The contrast that clarifies it:

• Divide and conquer (merge sort) has optimal substructure but the subproblems don't overlap — each half is sorted once. No caching needed → not DP.
• DP has optimal substructure and overlap → caching is the whole point.

When you see both conditions, reach for DP. In practice you spot overlap by writing the recursion and noticing it would call itself with the same arguments more than once.

Every DP boils down to answering two questions. Getting these right is solving the problem; the code is mechanical afterwards.

1. What is the state?

The state is the minimal set of variables that uniquely describes a subproblem. Write it as dp[...]. Ask: "What do I need to know to compute the answer for this subproblem, and nothing more?"

• dp[i] = answer considering the first i elements (or ending at index i).
• dp[i][c] = answer using items 0..i with capacity c (knapsack).
• dp[i][j] = answer for the cell at row i, column j (grids).

2. What is the transition?

The transition (a.k.a. the recurrence) expresses dp[state] in terms of smaller states. It encodes the choices available at this step.

Example — climbing stairs (reach step n taking 1 or 2 steps at a time):

dp[i] = dp[i-1] + dp[i-2]

State: dp[i] = number of ways to reach step i. Transition: the last move was either a 1-step (from i-1) or a 2-step (from i-2).

3. Base cases — the smallest states you can fill in directly, without a transition. For climbing stairs: dp[0] = 1 (one way to stand still), dp[1] = 1.

The DP recipe (memorise this):

Once you have the recurrence, there are three standard implementations. They compute the exact same thing — choose based on convenience and constraints.

Style 1 — plain recursion (slow, for understanding only). Just translate the recurrence. Correct but exponential when subproblems overlap.

Style 2 — top-down memoization (recursion + cache). Same recursion, but store each answer the first time and return it instantly afterwards.

Style 3 — bottom-up tabulation (iterative table fill). Drop recursion entirely; fill an array in an order that guarantees dependencies are ready.

All three turn O(2ⁿ) into O(n). The first is a teaching tool; the last two are what you submit.

Both are standard; pick per problem. Here is the honest contest comparison.

Practical advice for contests:

• Start top-down. It's the fastest path from "I understand the recurrence" to "I have working code," because it follows your recursive reasoning directly.
• Switch to bottom-up when (a) recursion depth might overflow the stack, (b) you need the last drop of speed, or (c) you want to space-optimise with a rolling array.

Many strong competitors write top-down by default and only convert when forced. Both are correct — use whichever gets you to AC faster.

The speed of a DP is captured by one simple formula:

Total time ≈ (number of distinct states) × (work per transition).

That's the single most useful thing to internalise. To estimate whether a DP will pass:

1. Count the states — the size of your dp table (e.g. n for dp[i], n·W for dp[i][w]).
2. Multiply by the cost of one transition — O(1) if it's a couple of lookups, O(k) if you loop over k choices.

Examples:

• Fibonacci: n states × O(1) = O(n).
• 0/1 knapsack: n·W states × O(1) = O(n·W).
• Coin change (min coins, amount A, m coins): A states × O(m) per state = O(A·m).
• Longest increasing subsequence (basic): n states × O(n) scan = O(n²).

Memoization guarantees each state is computed once; every later request is a cache hit. That "compute once, reuse forever" is exactly why exponential recursion collapses to polynomial DP.

If the state count alone already exceeds your time budget (say, 10⁹ states), the DP formulation is too coarse — you need a smaller state, a smarter transition, or a different technique.