Understand overlapping subproblems, optimal substructure, memoization, and tabulation.
Dynamic Programming solves problems with overlapping subproblems and optimal substructure by caching results. Two approaches: top-down (memoization) and bottom-up (tabulation).
Usually O(n) or O(n²)
O(n) or O(n²); often reducible
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
same sub-problem solved multiple times in recursion
optimal solution built from optimal sub-solutions
top-down: add a cache to recursion
bottom-up: fill a table iteratively
dp[i] = answer to sub-problem of size i
express dp[i] in terms of earlier dp values
initialize dp for the smallest inputs
if dp[i] depends only on dp[i-1], use two variables