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.
Table 1: Core Properties
| 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. |