Dynamic Programming: Foundations, Patterns, and How to Recognize a DP Problem

In plain words

Imagine computing the 50th Fibonacci number by hand, starting from scratch with the definition fib(50) = fib(49) + fib(48). You'd compute fib(48) once for the left branch, then again for the right branch's fib(49) = fib(48) + fib(47) — and fib(48) splits again, and again. The tree of calls doubles at every level: 2⁵⁰ calls for a single number. Now imagine keeping a notepad: the first time you compute fib(k), write it down. Next time someone asks, read the notepad instead of recomputing. With the notepad, fib(50) needs only 50 distinct computations. That notepad is dynamic programming.

Dynamic programming (DP) has an outsized reputation for difficulty, but its core idea is one you already met in Lesson 8: recursion that caches its results so it never solves the same subproblem twice. That's it. The difficulty is entirely in *recognizing* when DP applies and *defining the subproblem correctly*; the mechanics are trivial once those are settled. This lesson gives you a reliable framework for both.

                       fib(5)
                      /        \
                 fib(4)         fib(3)
                /      \       /     \
           fib(3)    fib(2) fib(2)  fib(1)
           /    \
        fib(2) fib(1)

fib(3) computed TWICE, fib(2) computed THREE times.
For fib(50): ~2^50 calls ≈ 10^15 — completely infeasible.

With memoization (notepad):
  fib(2) computed once, stored.
  fib(3) computed once (using stored fib(2)), stored.
  ...
  fib(50) needs exactly 50 distinct computations. O(n) time.

The recursion tree becomes a DAG (directed acyclic graph):
  each unique subproblem is a single node visited once.

The two conditions

• Overlapping subproblems: the naive recursion solves the same subproblem many times. Naive Fibonacci recomputes fib(3) billions of times for fib(50) — the tree is full of duplicates. (This is exactly what distinguishes DP from divide-and-conquer, whose subproblems are independent and don't repeat.)
• Optimal substructure: an optimal solution to the problem is built from optimal solutions to its subproblems. Shortest paths have it (a shortest path's sub-paths are shortest); longest *simple* paths don't (which is why DP solves the former but not the latter).

When both hold, DP transforms the exponential recursion tree into a polynomial computation by solving each *distinct* subproblem exactly once. Fibonacci: O(2ⁿ) → O(n), because there are only n distinct subproblems, not 2ⁿ.

Two implementations: memoization and tabulation

// ── Naive (exponential) ──────────────────────────────────────────────
function fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)          // O(2^n) — recomputes everything

// ── Top-down memoization ──────────────────────────────────────────────
memo = {}
function fib(n):
    if n <= 1: return n
    if n in memo: return memo[n]         // cache hit — O(1)
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]                       // O(n) time, O(n) space

// ── Bottom-up tabulation ──────────────────────────────────────────────
function fib(n):
    dp = array of size n+1
    dp[0] = 0; dp[1] = 1
    for i from 2 to n:
        dp[i] = dp[i-1] + dp[i-2]       // O(n) time, O(n) space
    return dp[n]

// ── Space-optimized tabulation (O(1) space) ───────────────────────────
function fib(n):
    prev2, prev1 = 0, 1
    for i from 2 to n:
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr                     // O(n) time, O(1) space
    return prev1

They compute the same answers; pick whichever is clearer for the problem. Memoization is often the fastest *route* to a working solution — write the plain recursion, then add a hash-map or array cache. Tabulation is often the fastest *runtime* and unlocks a further trick: when each state depends only on a few recent ones (as in Fibonacci, which needs just the last two), you can throw away the rest and drop space from O(n) to O(1). Many DP solutions optimize a 2D table down to two rows or one.

The framework: state, transition, base case, order

Every DP is four decisions. Get these right and the code writes itself:

1. Define the state. What does dp[i] (or dp[i][j]) *mean*? This is the hardest and most important step — a good state definition makes everything else fall out. E.g., 'dp[i] = length of the longest increasing subsequence ending at index i'.
2. Write the transition. How does a state's value come from smaller states? This is the recurrence, e.g., 'dp[i] = 1 + max(dp[j]) over all j < i with array[j] < array[i]'.
3. Set the base cases. The smallest states with direct answers — dp[0], an empty string, a zero-capacity knapsack.
4. Determine the order. Bottom-up must fill states before the states that depend on them; top-down handles this automatically via recursion.

The classic patterns

Most DP problems are variations of a handful of templates. Recognizing the template is 80% of solving:

• Linear / sequence DP: dp over positions in one array — climbing stairs, house robber, longest increasing subsequence, maximum subarray (Kadane's). State usually 'best answer ending at / using up to index i'.
• Knapsack DP: choose a subset under a constraint — 0/1 knapsack, subset sum, coin change, partition. State 'best value using the first i items with capacity c'. This is the pattern greedy failed on in Lesson 24.
• Two-sequence / grid DP: dp[i][j] over two strings or a 2D grid — edit distance, longest common subsequence, unique paths, minimum path sum. State 'answer for prefixes of length i and j'.
• Interval DP: dp over subranges [i, j] — matrix-chain multiplication, optimal BST, burst balloons. Build up from small intervals to large.
• DP on trees and DP with bitmask (subsets encoded as bits, Lesson 27) round out the advanced toolkit.

Worked example: coin change (fewest coins)

Given coin denominations and an amount, find the fewest coins that sum to it. State: dp[a] = fewest coins to make amount a. Transition: dp[a] = 1 + min over each coin c ≤ a of dp[a − c] (use one coin c, then optimally make the rest). Base case: dp[0] = 0. Order: fill a from 0 up to the target.

Coins: {1, 3, 4}    Amount: 6

amount:   0   1   2   3   4   5   6
dp[a]:    0   ?   ?   ?   ?   ?   ?

Fill:
  dp[0] = 0  (base case: 0 coins needed for amount 0)
  dp[1]: try coin 1 → dp[1-1]+1=dp[0]+1=1        → dp[1] = 1
  dp[2]: try coin 1 → dp[2-1]+1=dp[1]+1=2        → dp[2] = 2
  dp[3]: try coin 1 → dp[2]+1=3
         try coin 3 → dp[0]+1=1  ← min!          → dp[3] = 1
  dp[4]: try coin 1 → dp[3]+1=2
         try coin 3 → dp[1]+1=2
         try coin 4 → dp[0]+1=1  ← min!          → dp[4] = 1
  dp[5]: try coin 1 → dp[4]+1=2  ← min!
         try coin 3 → dp[2]+1=3
         try coin 4 → dp[1]+1=2                   → dp[5] = 2  (4+1)
  dp[6]: try coin 1 → dp[5]+1=3
         try coin 3 → dp[3]+1=2  ← min!
         try coin 4 → dp[2]+1=3                   → dp[6] = 2  (3+3)

amount:   0   1   2   3   4   5   6
dp[a]:    0   1   2   1   1   2   2

Answer: dp[6] = 2  (coins 3+3)
Greedy (by size, largest first): 4+1+1 = 3 coins — WORSE!
DP correctly finds the globally optimal 2-coin answer.

Worked example: longest common subsequence (two-sequence DP)

Given two strings, find the length of their longest common subsequence (characters in order, not necessarily contiguous). State: dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]. Transition: if s1[i-1]==s2[j-1], dp[i][j] = dp[i-1][j-1]+1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base: dp[0][j]=dp[i][0]=0.

s1 = "ABCBDAB"  (length 7)
s2 = "BDCAB"   (length 5)

dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]

     ""  B  D  C  A  B
  ""  0  0  0  0  0  0
  A   0  0  0  0  1  1
  B   0  1  1  1  1  2
  C   0  1  1  2  2  2
  B   0  1  1  2  2  3
  D   0  1  2  2  2  3
  A   0  1  2  2  3  3
  B   0  1  2  2  3  4

Answer: dp[7][5] = 4
One LCS: "BCAB" (or "BDAB")

Recurrence:
  s1[i-1]==s2[j-1] → dp[i][j] = dp[i-1][j-1] + 1  (extend match)
  otherwise         → dp[i][j] = max(dp[i-1][j], dp[i][j-1])  (skip one char)

Complexity: O(mn) time, O(mn) space (reducible to O(min(m,n)) with rolling rows).

How to recognize a DP problem

• The problem asks for an optimum ('minimum/maximum/longest/fewest') or a count of ways, over choices.
• You're making a sequence of decisions, and earlier decisions constrain later ones.
• A brute-force recursion would re-explore the same situations repeatedly (overlapping subproblems).
• Greedy plausibly fails (choices interact), and the answer depends on combinations, not a single locally best pick.
• Reliable tell: if you can phrase the answer as 'the best over a few smaller versions of the same problem', it's almost certainly DP.

Common pitfalls

• A wrong or vague state definition. The root cause of most DP failures. If the transition feels impossible to write, the state is wrong — redefine it before coding.
• Missing or incorrect base cases. Off-by-one at the boundary (empty string, amount 0, capacity 0) breaks the whole table.
• Wrong fill order in tabulation. A state computed before its dependencies reads garbage. Respect the dependency direction.
• Forgetting DP needs optimal substructure. Some optimization problems (longest simple path) lack it and can't be solved by DP.
• Over-applying DP. If subproblems don't overlap, plain divide-and-conquer is simpler; if the greedy-choice property holds, greedy is faster. DP is for overlapping subproblems where greedy fails.

Practice problems

1. Climbing stairs: you can climb 1 or 2 steps at a time; how many ways to reach step n? State: dp[i] = ways to reach step i. Transition: dp[i] = dp[i-1] + dp[i-2]. O(n) time, O(1) space.
2. 0/1 knapsack: n items each with weight and value, capacity W. dp[i][w] = max value using first i items with capacity w. O(nW) time and space (reduce to O(W) with rolling array).
3. Edit distance: minimum insertions, deletions, substitutions to transform string s into t. Two-sequence DP, O(mn) time. A classic for spell-checkers and diff tools.

Key takeaways

• DP = recursion + caching, applicable when subproblems overlap and solutions have optimal substructure.
• Two implementations: top-down memoization (recursion + cache) and bottom-up tabulation (iterative table); same results, different trade-offs.
• The framework is state → transition → base cases → fill order; defining the state well is the whole game.
• Learn the patterns (linear, knapsack, two-sequence/grid, interval); recognizing the template solves most of the problem.
• Reach for DP when you seek an optimum or a count over interacting sequential choices with repeated subproblems.

DP explores all choices but prunes via caching. The next paradigm explores all choices too, but prunes by *abandoning* dead branches early — backtracking. Drill DP state-definition and patterns in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play