54. Name classic DP problems and their recurrences.
MediumDynamic programming
Technical
Show model answer
Fibonacci / climbing stairs: f(n) = f(n−1) + f(n−2). 0/1 knapsack: best(i, c) = max(best(i−1, c), best(i−1, c − wᵢ) + vᵢ). Edit distance: 1 + min(replace, insert, delete) unless the characters match. Longest increasing subsequence: lis(i) = 1 + max lis(j) for j < i with a[j] < a[i]. Matrix chain multiplication: try every split point k. Coin change (fewest coins): dp[a] = 1 + min dp[a − c].