LeetCode · DP — 2D
Dynamic Programming — 2D Problem Set
Two-dimensional DP tables, string matching, grid traversal, and advanced state transitions. The hardest DP problems live here.
Concept page: Dynamic Programming
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Medium | grid | LC 62 · Unique Paths | dp[i][j] = dp[i-1][j] + dp[i][j-1]. O(m·n). |
| Medium | string | LC 5 · Longest Palindromic Substring | Expand around center or 2D DP. O(n²). |
| Medium | LCS | LC 1143 · Longest Common Subsequence | Classic 2D DP: match → dp[i-1][j-1]+1, else max(left, top). O(m·n). |
| Medium | knapsack | LC 494 · Target Sum | Subset sum variant with offset. O(n·sum). |
| Medium | unbounded | LC 518 · Coin Change II | Count combinations (not permutations). 2D or 1D space-optimised. O(n·amount). |
| Medium | state-machine | LC 309 · Best Time to Buy and Sell Stock with Cooldown | Three states: hold, sold, rest. O(n). |
| Medium | interleave | LC 97 · Interleaving String | dp[i][j] = can s1[0..i] + s2[0..j] form s3[0..i+j]? O(m·n). |
| Hard | edit | LC 72 · Edit Distance | Insert, delete, or replace. dp[i][j] = min operations. O(m·n). |
| Hard | regex | LC 10 · Regular Expression Matching | 2D DP handling '.' and '*'. O(m·n). |