What you'll learn

  1. Quick answer
  2. The Core Idea, Shown Once
  3. When DP Applies
  4. Memoization vs Tabulation
  5. A Method That Works on Unfamiliar Problems
  6. The Patterns Worth Recognising
  7. FAQ

Quick Answer

Dynamic programming solves problems by breaking them into subproblems and reusing answers instead of recomputing them. It applies when a problem has overlapping subproblems and optimal substructure. There are two styles: memoization, which is recursion plus a cache and is easier to write, and tabulation, which builds a table bottom-up and avoids recursion limits. The hard part is defining the state and the recurrence, not the code.

The Core Idea, Shown Once

The naive Fibonacci function is the clearest demonstration of the problem DP solves.

def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)

Correct, and unusably slow. Because fib(5) calls fib(3) twice, fib(2) three times, and so on — the same subproblems recomputed exponentially often. It is O(2ⁿ), so fib(50) takes minutes.

                fib(5)
           /            \
       fib(4)          fib(3)      ← computed again
      /     \          /    \
  fib(3)  fib(2)   fib(2)  fib(1)  ← and again

Store each answer the first time and the tree collapses to a line:

def fib(n, memo={}):
    if n <= 1: return n
    if n in memo: return memo[n]        # already solved
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

O(2ⁿ) becomes O(n). That is dynamic programming in its entirety — never solve the same subproblem twice. Everything else is deciding what the subproblems are.

(Note the mutable default argument here is a deliberate cache but a risky habit — in production pass the memo explicitly or use functools.cache.)

When DP Applies

Two properties must hold, and checking them is how you decide.

Overlapping subproblems. The same smaller problems recur. Fibonacci has them; merge sort does not — each half is sorted once, so caching would gain nothing. That is why divide and conquer is not DP.

Optimal substructure. The best solution is built from best solutions to subproblems. The shortest path from A to C through B contains the shortest path from A to B.

Signals in the problem statement:

  • "Find the maximum or minimum …"
  • "How many ways can you …"
  • "Is it possible to reach …"
  • Choices at each step, where earlier choices affect later options

Signals it is NOT DP: if a greedy choice is provably always safe, use greedy — it is simpler and faster. Activity selection by earliest finish time is greedy; the knapsack problem is not, because taking the highest-value item first can be wrong.

A practical way to decide: write the brute-force recursion first. If the recursion tree repeats subproblems, add a cache and you have a DP solution. That path is far more reliable than trying to write the table directly.

Memoization vs Tabulation

Two ways to write the same solution.

Memoization (top-down) — recursion with a cache. Write the natural recursion, then add storage.

from functools import cache

@cache                       # Python does the memoization for you
def climb(n):
    if n <= 2: return n
    return climb(n - 1) + climb(n - 2)

Advantages: closest to how you naturally think about the problem, and it only computes the states actually needed.
Disadvantages: recursion depth limits, and function-call overhead.

Tabulation (bottom-up) — build a table from the smallest cases upward.

def climb(n):
    if n <= 2: return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Advantages: no recursion limit, usually faster, and easy to optimise space.
Disadvantages: you must work out the correct fill order, and it computes every state whether needed or not.

Space optimisation is the standard follow-up. If each state only depends on the previous one or two, you do not need the whole table:

def climb(n):
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b if n > 1 else 1        # O(1) space

Interviewers frequently accept the table version, then ask you to reduce the space. Knowing this transformation is worth practising.

A Method That Works on Unfamiliar Problems

The difficulty is never the code — it is defining the state. Use this sequence.

1. Write the brute-force recursion. Ignore efficiency. What choice do you make at each step, and what does the problem become afterwards?

2. Identify the state. What arguments fully describe a subproblem? For the knapsack it is (item index, remaining capacity). For edit distance it is (position in string A, position in string B). Getting this right is most of the work.

3. Write the recurrence. Express the answer for a state in terms of smaller states.

# 0/1 knapsack: at each item, take it or skip it
dp[i][w] = max(
    dp[i-1][w],                              # skip
    dp[i-1][w - weight[i]] + value[i]        # take, if it fits
)

4. Define the base cases. The smallest subproblems with known answers — usually an empty input or a zero capacity.

5. Add memoization, or convert to a table if depth is a concern.

6. Optimise space if only the last row is needed.

Say this process out loud in an interview. Reaching the correct recurrence and then running out of time still demonstrates more than producing a memorised table with no explanation.

The Patterns Worth Recognising

Most DP interview questions are variations on a handful of shapes.

Fibonacci-style (1D). Each state depends on the previous one or two. Climbing stairs, house robber, min cost climbing stairs. State: one index.

0/1 knapsack. Take or skip each item, with a constraint. Subset sum, partition equal subset sum, target sum, and coin change with limited coins. State: (index, remaining capacity).

Unbounded knapsack. Items can be reused. Coin change for minimum coins, rod cutting. State: (index, remaining), but you stay on the same item after taking it.

Two-sequence DP. Comparing two strings or arrays. Longest common subsequence, edit distance, longest common substring. State: (index in A, index in B), and the table is 2D.

Interval DP. Answers built from ranges. Matrix chain multiplication, burst balloons, palindrome partitioning. State: (left, right).

Grid DP. Paths through a matrix. Unique paths, minimum path sum. State: (row, column).

Practice order that builds properly: climbing stairs, house robber, coin change, longest increasing subsequence, longest common subsequence, edit distance, 0/1 knapsack, then word break. Each introduces one new idea, and doing them in this order makes the later ones feel routine rather than novel.

Frequently Asked Questions

What is the difference between memoization and dynamic programming? Memoization is one way to implement DP — recursion with a cache, working top-down. Tabulation is the other, building a table bottom-up. Both are dynamic programming; they differ in direction and in their recursion-depth and space characteristics.
How do I know a problem needs DP? Look for overlapping subproblems and optimal substructure, usually signalled by asking for a maximum, minimum, count of ways, or feasibility, with choices at each step. Write the brute-force recursion first — if it repeats subproblems, caching turns it into DP.
Is dynamic programming the same as recursion? No. Recursion is the mechanism; DP is the strategy of not recomputing repeated subproblems. Plenty of recursion has no overlapping subproblems, such as merge sort, and gains nothing from caching.
Should I learn top-down or bottom-up first? Top-down memoization, because it follows the natural recursion and requires no fill order. Convert to tabulation when recursion depth is a problem or when you want the space optimisation, which is a common interview follow-up.
Which DP problems should I practise first? Climbing stairs, house robber, coin change, longest increasing subsequence, longest common subsequence, edit distance and 0/1 knapsack, in that order. Each adds one new idea and they cover most interview patterns.