Dynamic Programming
Dynamic programming (DP) is an algorithmic technique for solving problems by breaking them into overlapping subproblems, solving each subproblem once, and storing (caching) its result to avoid redundant recomputation.
Definition
Dynamic programming (DP) is an algorithmic technique for solving problems by breaking them into overlapping subproblems, solving each subproblem once, and storing (caching) its result to avoid redundant recomputation.
Overview
Dynamic programming applies to problems that exhibit two properties: optimal substructure, meaning an optimal solution can be built from optimal solutions to smaller subproblems, and overlapping subproblems, meaning the same subproblem is encountered repeatedly during a naive recursive solution. Classic examples include computing Fibonacci numbers, the knapsack problem, longest common subsequence, and shortest-path algorithms on graphs. There are two common ways to implement DP. Top-down (memoized recursion) writes the solution as a natural recursion but caches each subproblem's result the first time it's computed, so subsequent calls with the same inputs return instantly — this is memoization applied to a recursive algorithm. Bottom-up (tabulation) instead builds a table iteratively from the smallest subproblems up to the final answer, avoiding recursion and its call-stack overhead entirely. Both approaches typically reduce an exponential brute-force runtime, like the naive O(2ⁿ) recursive Fibonacci, down to polynomial time such as O(n). DP is closely tied to Big O Notation analysis because the whole point of the technique is trading extra memory (for the cache or table) for a large reduction in time complexity. It also overlaps with graph algorithms — many shortest-path and network-flow algorithms are themselves dynamic programming in disguise. DP is one of the more conceptually demanding topics in algorithm design, frequently appearing in technical interviews and competitive programming because recognizing that a problem has overlapping subproblems, and correctly defining the recurrence relation, requires real practice rather than rote memorization.
Key Concepts
- Requires optimal substructure and overlapping subproblems
- Top-down variant: recursion plus memoization/caching
- Bottom-up variant: iterative tabulation from base cases upward
- Trades additional memory for large reductions in time complexity
- Commonly reduces exponential-time brute force to polynomial time
- Used in classic problems: knapsack, edit distance, longest common subsequence
- Core building block for many shortest-path and optimization algorithms