dynamic-programming

Dynamic Programming

Overview

Dynamic programming (DP) is a method for solving problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the results to avoid redundant computation. Knuth discusses dynamic programming techniques throughout The Art of Computer Programming, particularly in the context of optimization, sequence analysis, and combinatorial problems. The term was coined by Richard Bellman in the 1950s.

Core Principles

Optimal Substructure

A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to its subproblems. This property allows us to build the global optimum from local optima.

Example: The shortest path from A to C through B consists of the shortest path from A to B plus the shortest path from B to C.

Overlapping Subproblems

A problem has overlapping subproblems when the same subproblems are solved repeatedly in a naive recursive approach. DP eliminates this redundancy by storing results.

Example: Computing Fibonacci(n) recursively recomputes Fibonacci(k) for each k < n exponentially many times.

Two Approaches

Memoization (Top-Down)

Start with the original problem, recurse into subproblems, and cache results as they are computed.

FIB_MEMO(n, cache):
    if n <= 1: return n
    if n in cache: return cache[n]
    cache[n] = FIB_MEMO(n - 1, cache) + FIB_MEMO(n - 2, cache)
    return cache[n]

Advantages: Natural to write (follows recursive structure), computes only the subproblems actually needed. Disadvantages: Recursion overhead, potential stack overflow for deep recursion.

Tabulation (Bottom-Up)

Build a table from the smallest subproblems up to the desired result, iterating in a careful order.

FIB_TABLE(n):
    if n <= 1: return n
    dp[0] = 0, dp[1] = 1
    for i = 2 to n:
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Advantages: No recursion overhead, easier to optimize space (often only need the last few entries). Disadvantages: May compute subproblems that are never needed, ordering can be less intuitive.