dynamic programming
Dynamic programming is the art of solving a problem by solving its smaller subproblems first and remembering their answers, so that no subproblem is ever solved twice. Despite the grand name (which historically had nothing to do with computer programming), the core idea is humble and powerful: when a problem keeps bumping into the same little questions over and over, write each answer down in a table and look it up instead of recomputing it. You trade some memory for a dramatic saving in time.
Two ingredients make a problem ripe for DP. First, overlapping subproblems: the naive recursion solves the same subproblem many times — think of how computing Fibonacci by recursion asks for fib(2) again and again. Second, optimal substructure: the best answer to the whole is built from the best answers to its parts, so once a subproblem's answer is settled it never needs revising. When both hold, you can fill a table of subproblem answers — either top-down with memoization (recurse, but cache each result) or bottom-up with tabulation (start from the smallest cases and build upward in a loop).
The payoff is often a leap from exponential to polynomial time. Fibonacci drops from O(2^n) to O(n). The 0/1 knapsack, longest common subsequence, edit distance, and shortest paths in a weighted graph all yield to DP, typically running in O(n·W) or O(n·m) — the size of the table times the work per cell. The skill is in spotting the right subproblem definition (the "state") and the recurrence that links states; once those are right, the code almost writes itself. The cost is the memory the table occupies, though clever DPs often keep only the last row or two.
long long fib(int n) {
if (n < 2) return n;
vector<long long> dp(n + 1);
dp[0] = 0; dp[1] = 1; // base cases
for (int i = 2; i <= n; ++i)
dp[i] = dp[i - 1] + dp[i - 2]; // optimal substructure
return dp[n]; // O(n) time and space
}O(n) time, O(n) space — and you can shrink it to O(1) space by keeping just two values.
Top-down (memoized recursion) and bottom-up (tabulation) are two faces of the same DP. Top-down is closer to how you think and only computes states you actually need; bottom-up avoids recursion overhead and makes it easy to shrink memory to the last few rows. The recurrence is the same either way.