Dynamic Programming
In one line
Dynamic programming solves complex problems by breaking them into overlapping sub-problems and caching their results.
In simple words
Dynamic programming (DP) is a technique for solving problems that have overlapping sub-problems and optimal substructure. You break the problem into smaller pieces, solve each piece once, and store (memoize) the result so you never recompute it. This turns exponential recursive solutions into polynomial ones.
The classic example is Fibonacci: naive recursion computes fib(2) many times. With memoization, each fib(n) is computed once and cached, reducing O(2^n) to O(n). Other DP problems include the knapsack problem, longest common subsequence, edit distance, and coin change.
DP can be implemented top-down (recursion + memo cache) or bottom-up (fill a table from smallest to largest). The bottom-up approach often uses an array and iterates, avoiding recursion overhead. Identifying the state and the recurrence relation is the hard part — once you have those, the code is usually straightforward.
Example
// Fibonacci with memoization (top-down DP)
const memo = {};
function fib(n) {
if (n <= 1) return n;
if (memo[n] !== undefined) return memo[n];
return memo[n] = fib(n - 1) + fib(n - 2);
}
console.log(fib(10)); // 55
console.log(fib(40)); // 102334155 — fast because results are cachedEach fib(n) is computed once and stored in memo. Subsequent calls return the cached value, turning O(2^n) into O(n).
Related terms
Related Resources
Related Lessons
- Algorithms
Learn dynamic programming.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.