Chapter 2 — Dynamic Programming
Source:
src/main/kotlin/dynamic_programming/,src/main/kotlin/array/dp/,src/main/kotlin/graph/dp/(and friends)Master idea: DP is organized recursion — the same subproblems, computed once, reused many times. Every DP in this book is: state → recurrence → base case → answer, and the “aha” is always discovering the right state.
Prerequisites: the recurrence math in Reference §4.
Problems at a glance
| # | Problem | State & recurrence essence | Complexity | Page |
|---|---|---|---|---|
| 2.1 | Longest Common Substring | dp[i][j] = length of common substring ending at (i,j) | $O(mn)$ | → |
| 2.2 | Minimum Edit Distance | dp[i][j] = edit distance of prefixes; min of insert/delete/replace | $O(mn)$ | → |
| 2.3 | Longest Common Subsequence | dp[i][j] = LCS of prefixes; match or skip | $O(mn)$ | → |
| 2.4 | 0/1 Knapsack | dp[c] = max value with capacity c; pick or skip | $O(nW)$ | → |
| 2.5 | Unbounded Knapsack | same, but dp[c] reuses the current item | $O(nW)$ | → |
| 2.6 | Partition Equal Subset Sum | subset-sum reachability; dp[s] boolean | $O(nS)$ | → |
| 2.7 | Maximum Product Subarray | track max AND min (sign flips!) | $O(n)$ | → |
| 2.8 | Frog Jump | set of reachable jumps per stone | $O(n^2)$ | → |
| 2.9 | Super Egg Drop | dp[k][m] = floors coverable with k eggs, m moves | $O(k \log f)$ | → |
| 2.10 | Minimum Cost To Cut A Stick | interval DP: dp[i][j] over sorted cut points | $O(n^3)$ | → |
| 2.11 | Minimum Cost To Merge Stones | interval DP with K-way grouping | $O(n^3)$ | → |
| 2.12 | Closest Subsequence Sum | meet-in-the-middle (see 1.22) | $O(2^{n/2} \log 2^{n/2})$ | → |
| 2.13 | Maximum Profit In Job Scheduling | sort + dp[i] = max profit up to job i | $O(n \log n)$ | → |
| 2.14 | Count Ways To Pick K Coins Divisible By M | memoized (idx, k, rem) | $O(nkm)$ | → |
| 2.15 | Maximal Square | min-of-three DP | $O(mn)$ | → |
| 2.16 | Coin Change | unbounded-knapsack minimization | $O(AC)$ | → |
| 2.17 | House Robber | include/exclude two-variable DP | $O(n)$ | → |
| 2.18 | Maximum Subarray | Kadane best-ending-here | $O(n)$ | → |
| 2.19 | Longest Increasing Subsequence | dp over all previous | $O(n^2)$ | → |
| 2.20 | Burst Balloons | interval DP + sentinels | $O(n^3)$ | → |
| 2.21 | Target Sum | (index, sum) memo | $O(nS)$ | → |
| 2.22 | Interleaving String | (i, j) matching memo | $O(mn)$ | → |
| 2.23 | Regular Expression Matching | (i, j) memo with * | $O(mn)$ | → |
| 2.24 | Delete Operations For Two Strings | LCS → deletions | $O(mn)$ | → |
| 2.25 | Cherry Pickup | two-walker DP | $O(n^3)$ | → |
| 2.26 | Racecar | (pos, speed) DFS | $O(win·sp)$ | → |
| 2.27 | Min Taps To Water Garden | interval covering greedy | $O(n)$ | → |
| 2.28 | Shortest Common Supersequence | LCS + backtrace | $O(mn)$ | → |
| 2.29 | Min Cost Climbing Stairs | two-step DP | $O(n)$ | → |
| 2.30 | Coin Change II | unbounded-knapsack count | $O(ca)$ | → |
| 2.31 | Unique Paths | grid DP / combinatorics | $O(mn)$ | → |
| 2.32 | Unique Paths II | obstacle-zeroed DP | $O(mn)$ | → |
| 2.33 | Palindrome Partitioning II | palindrome table + min cuts | $O(n^2)$ | → |
| 2.34 | Valid Palindrome III | LPS DP | $O(n^2)$ | → |
| 2.35 | Longest Palindromic Subsequence | LPS memo / LCS(s, rev) | $O(n^2)$ | → |
| 2.36 | Stone Game | relative-score range DP | $O(n^2)$ | → |
| 2.37 | Minimum Path Sum | grid min DP | $O(mn)$ | → |
| 2.38 | Continuous Subarray Sum | prefix-mod repetition | $O(n)$ | → |
| 2.39 | Number Of Zero-Filled Subarrays | run counting | $O(n)$ | → |
| 2.40 | Subarray Product Less Than K | sliding product | $O(n)$ | → |
| 2.41 | String Chain | sorted-length DP | $O(nL^2)$ | → |
| 2.42 | Partition Array Into Two Arrays | meet-in-the-middle | $O(2^{n/2}log)$ | → |
Reading order
2.2 and 2.3 first — they’re the ur-examples of the state-shape dp[i][j]. Then 2.1 (same table, different recurrence), then the knapsack family (2.4–2.6) which is the most frequently re-appearing pattern in real interviews, then the interval DPs (2.10, 2.11), then the gyms (2.8, 2.9, 2.13). End with 2.12 which is the anti-DP — it proves you know when not to reach for a DP table.