Dynamic Programming

Dynamic programming solves problems with overlapping subproblems by computing each subproblem once and reusing the stored result.

Solve each subproblem once

Dynamic programming (DP) applies when a problem has optimal substructure, meaning an optimal solution is built from optimal solutions to subproblems, and overlapping subproblems, meaning the same subproblems recur many times. DP computes each subproblem exactly once and stores its answer, replacing exponential recomputation with polynomial work.

Top-down and bottom-up

There are two styles. Top-down DP writes the natural recursion and adds memoization to cache results. Bottom-up DP fills a table in an order that guarantees every needed subproblem is solved before it is used, replacing recursion with loops. Both do the same total work; bottom-up avoids call-stack overhead and often enables space savings.

• Optimal substructure: optima built from sub-optima
• Overlapping subproblems: the same subproblems recur
• Top-down: recursion plus a cache
• Bottom-up: iterative table filling

A worked example

python

def fib(n):
    dp = [0, 1] + [0]*(n-1)
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]  # O(n) time, O(1) space if only two values kept

Classic problems

Dynamic programming solves the knapsack problem, longest common subsequence, edit distance, matrix-chain ordering, and shortest paths via Bellman-Ford and Floyd-Warshall. The design skill is identifying the state that captures a subproblem and the recurrence that relates states.

Where it fits versus greedy

When a greedy local choice is provably optimal, a greedy algorithm is simpler and faster. Dynamic programming is needed when local choices interact and you must consider combinations of subproblem solutions to find the true optimum.