Dynamic Programming

Dynamic programming solves problems with overlapping subproblems by storing subresults, turning exponential recomputation into polynomial time.

The core idea

Dynamic programming (DP) applies when a problem breaks into subproblems that recur many times. Instead of recomputing each subproblem, DP solves each once and stores the result, reusing it whenever it reappears. This converts an exponential recursion into a polynomial-time algorithm.

Two requirements

• Optimal substructure: an optimal solution is built from optimal solutions to subproblems
• Overlapping subproblems: the same subproblems arise repeatedly during the computation

Memoization versus tabulation

There are two implementation styles. Top-down memoization keeps the natural recursion but caches results as they are computed. Bottom-up tabulation fills a table of subresults in dependency order, avoiding recursion entirely. Both achieve the same complexity; the choice is a matter of clarity and constant factors.

A worked example

Naive recursive Fibonacci recomputes the same values exponentially, taking O(2^n) time. Storing each value as it is computed makes it O(n).

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

Classic applications

• Shortest paths (Bellman-Ford, Floyd-Warshall)
• Sequence alignment and edit distance
• Knapsack with integer weights
• Matrix chain multiplication ordering

The pseudo-polynomial caveat

DP can make some NP-hard problems, like knapsack, solvable in time polynomial in the numeric values involved. But that value can be exponential in the input's bit length, so the algorithm is only pseudo-polynomial, not truly polynomial. DP tames overlap; it does not repeal NP-hardness.