# Dynamic Programming
Confidence: high
Last verified: 2026-05-22
Generation: human_only


## TL;DR

DP solves problems by breaking them into overlapping subproblems, solving each once (memoization/tabulation). Converts exponential to polynomial time. Requires optimal substructure. Classic: Fibonacci, knapsack, LCS, edit distance.

## Core Explanation

Top-down: recursion + cache (memoization). Bottom-up: iterative table filling (tabulation). 0/1 Knapsack: max value from n items with weight limit — O(nW) pseudo-polynomial. Longest Common Subsequence: O(mn). DP vs. greedy: greedy makes locally optimal choice (may fail globally); DP explores all possibilities via subproblem decomposition.

## Further Reading

- [Introduction to Algorithms (CLRS)](undefined)