Dynamic Programming

An optimization technique that solves problems by combining solutions to overlapping subproblems and storing intermediate results to avoid recomputation.

Category: Computer Science · Created: 2026-08-18 · Updated: 2026-08-18

Dynamic programming (DP) is a method for solving problems that have two properties: optimal substructure, meaning an optimal solution is built from optimal solutions of smaller subproblems, and overlapping subproblems, meaning the same subproblem is solved many times by a naive recursive algorithm. DP avoids the repeated work by computing each subproblem once and storing the result, trading memory for time. The name was coined by Richard Bellman in the 1940s; the same relaxation idea powers the Bellman–Ford algorithm, which is itself a dynamic program over paths.

The classic example is the Fibonacci sequence. The naive recursion fib(n) = fib(n−1) + fib(n−2) recomputes the same values exponentially often; storing results in a table (bottom-up) or a memo (top-down) reduces the cost to O(n). The two standard styles are top-down with memoization — a recursive function that caches answers in a hash table or array — and bottom-up tabulation, which fills the table in dependency order and is often iterative.

// bottom-up Fibonacci
function fib(n):
    table = [0, 1]
    for i = 2 to n:
        table[i] = table[i-1] + table[i-2]
    return table[n]

DP is used wherever an optimization can be decomposed into ordered decisions: shortest paths in graphs with acyclic structure, sequence alignment in bioinformatics, the knapsack problem, coin change, longest common subsequence, edit distance, and dynamic resource allocation in economics. The recurrence relation and its base cases are the core of any DP solution; choosing the state definition well is the main design skill. DP's cost analysis — how much time and space the table requires — is a central Big O exercise, and many exponential-looking problems become polynomial when their overlapping structure is exploited.

Dynamic Programming

Tags

Related articles