Dynamic Programming (1D, 2D, Knapsack, Range DP)

Dynamic Programming (1D, 2D, Knapsack, Range DP)

Dynamic programming has a reputation for being hard, and the reputation is half-deserved: the technique is simple, but seeing that a problem wants it takes practice. The technique is just this: when a recursive solution keeps solving the same smaller problem over and over, solve each one once and write the answer down. That is the entire idea. Everything else is figuring out what the "smaller problem" is.

The classic tell is a recursion whose branches overlap. Computing the n-th Fibonacci number by naive recursion recomputes fib(n-2) an exponential number of times; the moment you store each result, the exponential collapses to linear. Two ingredients have to be present for this to work: overlapping subproblems, so there is something worth caching, and optimal substructure, so an optimal answer is built from optimal answers to the pieces. When both hold, you define a state, write a recurrence relating it to smaller states, and fill a table.

From exponential to polynomial: solve each subproblem once

Remember the coin-change problem, where greedy failed? Making 6 from coins [1, 3, 4], greedy grabbed the 4 and needed three coins; the real optimum is two 3s. DP gets it right, because it does not commit to a choice, it considers every coin at every amount and keeps the best. The state is "fewest coins to make amount a," and the recurrence says: to make a, try each coin c and add one to the best way of making a - c.

def min_coins(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount              # dp[a] = fewest coins to make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Filling the table for coins = [1, 3, 4] up to 6:

dp[6] = 2, the two 3s, found because dp[6] looked back at dp[3] + 1 and preferred it to greedy's path. Each entry is computed once from earlier entries, so the whole thing is O(amount * coins), polynomial where the naive recursion was exponential.

In the wild: edit distance

The most quietly ubiquitous DP is edit distance, the minimum number of single-character insertions, deletions, or substitutions to turn one string into another. It powers spell-check suggestions, fuzzy search, the diff in your version control, and DNA sequence alignment in bioinformatics. The state is two-dimensional: dp[i][j] is the distance between the first i characters of one string and the first j of the other.

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                       # delete i chars to reach empty
    for j in range(n + 1):
        dp[0][j] = j                       # insert j chars from empty
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]         # characters match, no new cost
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],    # delete from a
                                   dp[i][j - 1],    # insert into a
                                   dp[i - 1][j - 1])# substitute
    return dp[m][n]

It is the same move as coin change, one dimension up: define what a partial answer means, write how it depends on smaller partial answers, fill the grid in an order where the dependencies are ready. That "three neighbors" recurrence, the cell above, the cell to the left, and the diagonal, is one of the most reused shapes in all of computing, and once you recognize it, a whole family of string and sequence problems stops being scary.

The trigger

You can phrase the answer as a choice that leaves a smaller version of the same problem, and the naive recursion would revisit the same smaller problems again and again. Words like "minimum," "maximum," "count the ways," or "is it possible," over sequences, grids, or a budget, are strong hints. If greedy feels almost right but you can build a counterexample, DP is usually the honest answer.

Where it shows up

• 1D DP: Fibonacci, climbing stairs, house robber, coin change, longest increasing subsequence.
• 2D DP: grid path counting and minimization, edit distance, longest common subsequence.
• Knapsack and range DP: budget allocation with weights and values, and interval problems like matrix-chain multiplication.

Where it bites

The hard part is never the loop, it is defining the state and the recurrence correctly; get the state wrong and nothing downstream can save you. After that, watch two things: the iteration order must respect dependencies, so a cell is only read after the cells it needs are filled, and base cases must be seeded exactly. Memory is the last trap and often the easy win: many 2D DPs only ever look one row back, so they collapse to O(n) space.

When it is the wrong tool

If the subproblems do not actually overlap, DP's table is pure overhead, and plain Divide & Conquer or recursion is simpler and just as fast. If the problem has the greedy-choice property, a Greedy algorithm gets the same answer without the memory of a table, so do not reach for DP out of habit when a proven greedy exists. And if the state space itself is astronomically large, filling a table is infeasible, and you fall back to heuristics, approximation, or a smarter formulation.

Its neighbors

DP is what Divide & Conquer becomes once the subproblems overlap and you add memoization. It is the counterpart to Greedy, trading commitment for the ability to reconsider. And it is often the optimization of a Backtracking search, caching the repeated subproblems that brute-force exploration would recompute.

References

• Introduction to Algorithms (CLRS), 4th ed., Cormen, Leiserson, Rivest, Stein, 2022
• The Algorithm Design Manual, 3rd ed., Steven Skiena, 2020