Dynamic programming

Dynamic programming (DP) is what you reach for when a problem decomposes into overlapping subproblems — you solve each subproblem once and cache the answer, turning exponential recursion into polynomial iteration. Two styles: top-down (write the recursion, add memoisation — a dictionary of already-solved inputs) and bottom-up (fill a table from base cases upward). The cues that DP applies: you see yourself computing fib(10) inside fib(11) and fib(12), or the problem smells like "best/longest/count over all subsequences". Classic examples: Fibonacci (dumb but teaches the pattern), longest common subsequence (used in git diff), edit distance (used in spellcheckers), knapsack (resource allocation). Spotting when DP applies is 80% of the skill — the code is usually short.