Dynamic Programming
Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them into overlapping subproblems, solving each subproblem only once, and storing results to avoid redundant computation (memoization or tabulation). It applies when a problem exhibits two key properties: optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems. DP is used in sequence alignment, shortest-path problems, knapsack optimization, and compiler design.
Key Formula
OPT(n) = max over items i of (value_i + OPT(remaining capacity after item i))
LaTeX: OPT(n) = \max_{1 \le i \le n} \left( v_i + OPT(n - w_i) \right)
| Symbol | Meaning | Unit |
|---|---|---|
| OPT(n) | Optimal value achievable with capacity n | value units |
| v_i | Value of item i | value units |
| w_i | Weight of item i | weight units |
| n | Remaining knapsack capacity | weight units |
Worked Example
Problem
Fibonacci sequence: compute F(5) using DP tabulation. F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).
Solution
Step 1: Create table dp[0..5], set dp[0]=0, dp[1]=1. Step 2: dp[2] = dp[1] + dp[0] = 1 + 0 = 1. Step 3: dp[3] = dp[2] + dp[1] = 1 + 1 = 2. Step 4: dp[4] = dp[3] + dp[2] = 2 + 1 = 3. Step 5: dp[5] = dp[4] + dp[3] = 3 + 2 = 5. Time complexity: O(n). Naive recursion would be O(2^n) without memoization.
Answer
F(5) = 5. DP reduces exponential naive recursion to linear O(n) time with O(n) space.
Dynamic Programming Approaches Comparison
| Approach | Direction | Storage | Call Overhead | Example |
|---|---|---|---|---|
| Top-Down (Memoization) | Recursive | Hash map / array | Yes (call stack) | Recursive Fibonacci + cache |
| Bottom-Up (Tabulation) | Iterative | Array | No | Iterative Fibonacci table |
| Space-Optimized DP | Iterative | O(1) or rolling array | No | Fibonacci with 2 variables |
| Bitmasked DP | Iterative/Recursive | Array indexed by bitmask | Sometimes | Travelling Salesman Problem |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Memoization
Memoization is an optimization technique that stores (caches) the results of expensive function calls and returns the cached result when the same inputs occur again, avoiding redundant computation in recursive algorithms. It is the top-down implementation strategy of dynamic programming, transforming an exponential-time naive recursion into polynomial time by ensuring each subproblem is solved only once. Memoization is used in recursive Fibonacci, shortest-path computations, and natural language parsing.
Recursion
Recursion is a programming and mathematical technique in which a function calls itself with a smaller or simpler version of the original problem, progressing toward one or more base cases that terminate the chain of calls. Every recursive solution requires a base case (stopping condition) and a recursive case (self-referential reduction). Recursion is fundamental to tree traversal, divide-and-conquer algorithms, backtracking, and functional programming.
Greedy Algorithm
A Greedy Algorithm is an algorithmic paradigm that makes the locally optimal choice at each step with the hope of finding a globally optimal solution, without reconsidering previous choices. Greedy algorithms are efficient and simple, but they do not always produce the globally optimal solution — they work correctly only when the problem satisfies the greedy-choice property and optimal substructure. Classic examples include Kruskal's and Prim's algorithms for minimum spanning trees, Huffman coding, and activity selection.
Coined by Richard Bellman in the 1950s. "Dynamic" was chosen to describe the time-varying nature of the problems, and "programming" referred to planning/optimization (as in "linear programming"), not computer programming. Bellman chose the term partly to avoid scrutiny from his military research sponsor.