Dynamic Programming (DP) is an algorithmic optimization technique that solves complex problems by breaking them into overlapping subproblems, storing their solutions to avoid redundant computation. Developed by Richard Bellman in the 1950s, DP applies to problems exhibiting optimal substructure (where optimal solutions contain optimal sub-solutions) and overlapping subproblems (where the same smaller problems recur multiple times). The key insight is that memoization or tabulation transforms exponential-time recursive algorithms into polynomial-time solutions by trading computation for memory — storing intermediate results in a cache or table rather than recalculating them repeatedly. Understanding when and how to apply DP, and recognizing its patterns across knapsack variants, string algorithms, grid traversals, graph algorithms, and tree problems, is essential for solving optimization challenges efficiently.
What This Cheat Sheet Covers
This topic spans 17 focused tables and 121 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
Table 1: Core Properties
Before any DP solution exists, a problem has to actually qualify for one — and these are the building blocks that decide it. Overlapping subproblems and optimal substructure are the two prerequisites; memoization, tabulation, state, transition, and base case are the five pieces you assemble once those prerequisites hold. Get comfortable naming each of these in a problem and the rest of the cheat sheet falls into place.
| Property | Example | Description |
|---|---|---|
Fibonacci: fib(5) calls fib(3) twice | • Same smaller problems are solved multiple times in naive recursion • DP caches results to avoid recomputation. | |
Shortest path: optimal path to C via B uses optimal path to B | Optimal solution contains optimal solutions to its subproblems — enables building the global optimum from local optima. | |
memo[n] = compute(n) | Top-down caching: stores results of recursive function calls in a lookup table (dict/map) on first computation. | |
dp[i] = dp[i-1] + dp[i-2] | • Bottom-up iterative: fills a table starting from base cases, building up to the final solution • no recursion overhead. |