| Climbing Stairs |
O(n) |
Counting paths / Fibonacci family — "how many ways to reach step N", |
| Coin Change |
O(amount * len(coins)) |
Classic "minimum cost to reach target" DP. Any problem where you choose |
| Constraint Satisfaction |
Exponential worst case, but constraint propagation prunes |
Puzzle solving, scheduling, configuration — "Sudoku", "N-Queens via |
| Edit Distance |
O(m * n) |
String similarity / diff algorithms — "minimum edits", "Levenshtein |
| Knapsack |
O(n * W) |
Resource allocation with constraints — "maximize value under weight |
| Longest Common Subseq |
O(m * n) |
Diff / alignment — "longest common subsequence", "diff two files", |
| Longest Increasing Subseq |
O(n log n) |
Patience sorting / longest chain — "longest increasing subsequence", |
| Traveling Salesman Dp |
O(n^2 * 2^n) |
Visit-all-nodes optimization — "shortest route visiting every city", |