You know the basics — memoization, tabulation, the 5-step framework. Now it's time to level up. Advanced DP problems aren't harder because of the technique; they're harder because of pattern recognition. If you can look at a problem and say, "Oh, this is a knapsack variant," or "This is string DP — I need a 2D table on both strings," you're already 80% of the way to a solution. The recurrence almost writes itself once you identify the pattern. That's the skill we're building today. This guide assumes you're comfortable with the fundamentals: overlapping subproblems, optimal substructure, memoization, tabulation, and the idea that DP is just recursion without redundant work. If any of that sounds fuzzy, go back to DP 101 first. Seriously. What follows is built on that foundation. We're going to cover seven major DP pattern families, each with multiple classic problems, full TypeScript implementations, visual table walkthroughs, and Big O analysis. By the end, you'll have a mental catalog of patterns and the ability to match new problems to the right one. > "The struggle with DP isn't writing the code. It's recognizing the shape of the problem. Learn the shapes, and the code follows." Let's get into it. --- ## Pattern 1: String DP (Two Strings) String DP problems are among the most common in interviews. The pattern is distinctive: you have **two strings** (or sometimes one string compared against itself), and you need to find some optimal relationship between them. The signature setup: a **2D table** where `dp[i][j]` represents the answer for `text1[0..i-1]` and `text2[0..j-1]`. Row 0 and column 0 represent empty strings. You fill the table by comparing characters and making decisions. > Whenever you see a problem involving two strings and words like "subsequence," "edit," "match," or "transform" — think String DP. --- ### Longest Common Subsequence (LeetCode 1143) **Problem**: Given two strings `text1` and `text2`, return the length of their longest common subsequence. A subsequence is a sequence that can be derived from a string by deleting some (or no) characters without changing the order of the remaining characters. This is the quintessential 2D string DP problem. Every string DP problem borrows ideas from LCS. **The Recurrence**: For each pair of characters `text1[i-1]` and `text2[j-1]`: - If they **match**: `dp[i][j] = dp[i-1][j-1] + 1` (extend the subsequence) - If they **don't match**: `dp[i][j] = max(dp[i-1][j], dp[i][j-1])` (take the better option — skip one character from either string) **Visual Walkthrough**: `text1 = "abcde"`, `text2 = "ace"` ``` "" a c e "" [ 0, 0, 0, 0 ] a [ 0, 1, 1, 1 ] b [ 0, 1, 1, 1 ] c [ 0, 1, 2, 2 ] d [ 0, 1, 2, 2 ] e [ 0, 1, 2, 3 ] ``` Reading the table: `dp[5][3] = 3`. The LCS is `"ace"` with length 3. - At `(1,1)`: `a == a` → `dp[0][0] + 1 = 1` - At `(3,2)`: `c == c` → `dp[2][1] + 1 = 2` - At `(5,3)`: `e == e` → `dp[4][2] + 1 = 3` **TypeScript Implementation**: ```typescript function longestCommonSubsequence(text1: string, text2: string): number { const m = text1.length; const n = text2.length; const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0) ); for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (text1[i - 1] === text2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } ``` **Space Optimization**: Since each row only depends on the previous row, we can use two 1D arrays: ```typescript function longestCommonSubsequenceOptimized(text1: string, text2: string): number { const m = text1.length; const n = text2.length; let prev = new Array(n + 1).fill(0); let curr = new Array(n + 1).fill(0); for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (text1[i - 1] === text2[j - 1]) { curr[j] = prev[j - 1] + 1; } else { curr[j] = Math.max(prev[j], curr[j - 1]); } } [prev, curr] = [curr, prev]; curr.fill(0); } return prev[n]; } ``` **Big O**: Time O(m × n), Space O(min(m, n)) with optimization. --- ### Edit Distance (LeetCode 72) **Problem**: Given two strings `word1` and `word2`, return the minimum number of operations required to convert `word1` into `word2`. You can insert, delete, or replace a character. This is one of the most elegant DP problems. Three possible operations means three transitions at each cell. **The Recurrence**: - If `word1[i-1] === word2[j-1]`: `dp[i][j] = dp[i-1][j-1]` (characters match, no operation needed) - Otherwise: `dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])` - `dp[i-1][j-1] + 1` → **Replace** `word1[i-1]` with `word2[j-1]` - `dp[i-1][j] + 1` → **Delete** `word1[i-1]` - `dp[i][j-1] + 1` → **Insert** `word2[j-1]` **Base cases**: `dp[i][0] = i` (delete all characters), `dp[0][j] = j` (insert all characters). **Visual Walkthrough**: `word1 = "horse"`, `word2 = "ros"` ``` "" r o s "" [ 0, 1, 2, 3 ] h [ 1, 1, 2, 3 ] o [ 2, 2, 1, 2 ] r [ 3, 2, 2, 2 ] s [ 4, 3, 3, 2 ] e [ 5, 4, 4, 3 ] ``` Answer: `dp[5][3] = 3`. Operations: replace `h→r`, delete `r`, delete `e`. - `(2,2)`: `o == o` → `dp[1][1] = 1` - `(4,3)`: `s == s` → `dp[3][2] = 2` - At `(5,3)`: `e != s` → `1 + min(dp[4][2], dp[4][3], dp[5][2]) = 1 + min(3, 2, 4) = 3` **TypeScript Implementation**: ```typescript function minDistance(word1: string, word2: string): number { const m = word1.length; const n = word2.length; const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0) ); for (let i = 0; i <= m; i++) dp[i][0] = i; for (let j = 0; j <= n; j++) dp[0][j] = j; for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (word1[i - 1] === word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = 1 + Math.min( dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1] ); } } } return dp[m][n]; } ``` **Big O**: Time O(m × n), Space O(m × n) — can be optimized to O(n). --- ### Longest Palindromic Subsequence (LeetCode 516) **Problem**: Given a string `s`, find the length of the longest palindromic subsequence. **The Trick**: The longest palindromic subsequence of `s` is the **LCS of `s` and `reverse(s)`**. That's it. If you know LCS, you know this problem. Why does this work? A palindrome reads the same forwards and backwards. So any common subsequence between `s` and its reverse is guaranteed to be a palindrome. ```typescript function longestPalindromeSubseq(s: string): number { const reversed = s.split('').reverse().join(''); return longestCommonSubsequence(s, reversed); } ``` Alternatively, you can solve it directly with interval-style DP on a single string: ```typescript function longestPalindromeSubseqDirect(s: string): number { const n = s.length; const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0) ); for (let i = 0; i < n; i++) dp[i][i] = 1; for (let len = 2; len <= n; len++) { for (let i = 0; i <= n - len; i++) { const j = i + len - 1; if (s[i] === s[j]) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; } ``` **Big O**: Time O(n²), Space O(n²). --- ### Distinct Subsequences (LeetCode 115) **Problem**: Given strings `s` and `t`, return the number of distinct subsequences of `s` which equals `t`. This one is about **counting matches**, not finding the longest. For each character, we decide: does this character in `s` participate in forming `t`, or do we skip it? **The Recurrence**: - If `s[i-1] === t[j-1]`: `dp[i][j] = dp[i-1][j-1] + dp[i-1][j]` - Use this character (inherit count from matching both) **plus** skip this character (inherit count from skipping `s[i-1]`) - If they don't match: `dp[i][j] = dp[i-1][j]` (can only skip) **Base cases**: `dp[i][0] = 1` for all `i` (empty `t` can always be matched), `dp[0][j] = 0` for `j > 0`. **Visual Walkthrough**: `s = "rabbbit"`, `t = "rabbit"` ``` "" r a b b i t "" [ 1, 0, 0, 0, 0, 0, 0 ] r [ 1, 1, 0, 0, 0, 0, 0 ] a [ 1, 1, 1, 0, 0, 0, 0 ] b [ 1, 1, 1, 1, 0, 0, 0 ] b [ 1, 1, 1, 2, 1, 0, 0 ] b [ 1, 1, 1, 3, 3, 0, 0 ] i [ 1, 1, 1, 3, 3, 3, 0 ] t [ 1, 1, 1, 3, 3, 3, 3 ] ``` Answer: `dp[7][6] = 3`. There are 3 distinct subsequences. ```typescript function numDistinct(s: string, t: string): number { const m = s.length; const n = t.length; const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0) ); for (let i = 0; i <= m; i++) dp[i][0] = 1; for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][j]; if (s[i - 1] === t[j - 1]) { dp[i][j] += dp[i - 1][j - 1]; } } } return dp[m][n]; } ``` **Big O**: Time O(m × n), Space O(m × n). > **String DP Takeaway**: Two strings → 2D table. Row/column 0 = empty string. At each cell, compare characters and decide what to do when they match vs. don't match. The recurrence depends on the problem, but the structure is always the same. --- ## Pattern 2: Decision Making (Take or Skip) This is the **knapsack family**. The core idea: for each item, you have a binary choice — **take it** or **skip it**. Each choice has consequences (value gained, capacity consumed, constraints violated), and you want the optimal outcome. If you see a problem that says "given a set of items with properties, maximize/minimize something subject to a constraint" — it's probably knapsack. --- ### House Robber II (LeetCode 213) **Problem**: Houses are arranged in a circle. You can't rob two adjacent houses. What's the maximum you can rob? **The Insight**: Since the first and last houses are adjacent in a circle, you **can't rob both**. So run the standard House Robber on two ranges: 1. Houses `0` to `n-2` (include first, exclude last) 2. Houses `1` to `n-1` (exclude first, include last) Take the max of both runs. ```typescript function rob(nums: number[]): number { if (nums.length === 1) return nums[0]; if (nums.length === 2) return Math.max(nums[0], nums[1]); function robLinear(houses: number[], start: number, end: number): number { let prevTwo = 0; let prevOne = 0; for (let i = start; i <= end; i++) { const current = Math.max(prevOne, prevTwo + houses[i]); prevTwo = prevOne; prevOne = current; } return prevOne; } return Math.max( robLinear(nums, 0, nums.length - 2), robLinear(nums, 1, nums.length - 1) ); } ``` **Big O**: Time O(n), Space O(1). > Circular DP trick: break the circle by running two linear passes with different boundary conditions. This pattern shows up in many circular problems. --- ### 0/1 Knapsack **Problem**: Given `n` items with weights and values, and a knapsack of capacity `W`, maximize the total value without exceeding the weight capacity. Each item can be used **at most once**. This is the **granddaddy** of decision-making DP. Countless interview problems are knapsack variants in disguise. **The Recurrence**: `dp[i][w]` = max value using items `0..i-1` with capacity `w`. - **Skip item i**: `dp[i][w] = dp[i-1][w]` - **Take item i** (if `weights[i-1] <= w`): `dp[i][w] = dp[i-1][w - weights[i-1]] + values[i-1]` - Take the max of both options. **Visual Walkthrough**: `weights = [1, 3, 4, 5]`, `values = [1, 4, 5, 7]`, `capacity = 7` ``` Cap: 0 1 2 3 4 5 6 7 No items: [ 0, 0, 0, 0, 0, 0, 0, 0 ] Item 1 (1,1): [ 0, 1, 1, 1, 1, 1, 1, 1 ] Item 2 (3,4): [ 0, 1, 1, 4, 5, 5, 5, 5 ] Item 3 (4,5): [ 0, 1, 1, 4, 5, 6, 6, 9 ] Item 4 (5,7): [ 0, 1, 1, 4, 5, 7, 8, 9 ] ``` Answer: `dp[4][7] = 9` (take items 2 and 3 with weights 3+4=7, values 4+5=9). **TypeScript (2D)**: ```typescript function knapsack01( weights: number[], values: number[], capacity: number ): number { const n = weights.length; const dp: number[][] = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0) ); for (let i = 1; i <= n; i++) { for (let w = 0; w <= capacity; w++) { dp[i][w] = dp[i - 1][w]; if (weights[i - 1] <= w) { dp[i][w] = Math.max( dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1] ); } } } return dp[n][capacity]; } ``` **1D Space Optimization** — this is critical and the trick is **iterating capacity in reverse**: ```typescript function knapsack01Optimized( weights: number[], values: number[], capacity: number ): number { const dp = new Array(capacity + 1).fill(0); for (let i = 0; i < weights.length; i++) { for (let w = capacity; w >= weights[i]; w--) { dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]); } } return dp[capacity]; } ``` > **Why reverse?** When iterating left to right, `dp[w - weights[i]]` might already be updated in this iteration, meaning you'd use item `i` more than once. Iterating right to left ensures you're always reading from the "previous row" — guaranteeing each item is only used once. This is the single most important detail in 0/1 knapsack. **Big O**: Time O(n × W), Space O(W) with optimization. --- ### Target Sum (LeetCode 494) **Problem**: Given an array `nums` and a target, assign `+` or `-` to each number to make the sum equal to the target. Return the number of ways. **The Knapsack Disguise**: Split the array into two groups: positives `P` and negatives `N`. - `P - N = target` - `P + N = totalSum` - Therefore: `P = (target + totalSum) / 2` Now the problem becomes: **count the number of subsets that sum to `P`** — a classic 0/1 knapsack (counting variant). ```typescript function findTargetSumWays(nums: number[], target: number): number { const totalSum = nums.reduce((a, b) => a + b, 0); if ((target + totalSum) % 2 !== 0) return 0; if (Math.abs(target) > totalSum) return 0; const subsetSum = (target + totalSum) / 2; const dp = new Array(subsetSum + 1).fill(0); dp[0] = 1; for (const num of nums) { for (let s = subsetSum; s >= num; s--) { dp[s] += dp[s - num]; } } return dp[subsetSum]; } ``` **Big O**: Time O(n × sum), Space O(sum). --- ### Partition Equal Subset Sum (LeetCode 416) **Problem**: Given an array, determine if it can be partitioned into two subsets with equal sum. **The Knapsack Connection**: If the total sum is odd, it's impossible. If even, find a subset that sums to `totalSum / 2`. ```typescript function canPartition(nums: number[]): boolean { const totalSum = nums.reduce((a, b) => a + b, 0); if (totalSum % 2 !== 0) return false; const target = totalSum / 2; const dp = new Array(target + 1).fill(false); dp[0] = true; for (const num of nums) { for (let s = target; s >= num; s--) { dp[s] = dp[s] || dp[s - num]; } } return dp[target]; } ``` **Big O**: Time O(n × sum), Space O(sum). > **Decision Making Takeaway**: "Take or skip" problems are 0/1 knapsack. Convert the problem to the form "select a subset from items to optimize/count something subject to a constraint." Then apply the template. The 1D optimization with reverse iteration is essential knowledge. --- ## Pattern 3: Unbounded Knapsack (Take Unlimited) The unbounded knapsack differs in one key way: **you can use each item as many times as you want**. This changes the inner loop direction from reverse (0/1) to **forward** (unbounded). --- ### Coin Change (LeetCode 322) — Unbounded Lens You've likely seen Coin Change before. Let's re-examine it through the unbounded knapsack framework. **Problem**: Given coin denominations and an amount, find the fewest coins to make that amount. Each coin can be used unlimited times → unbounded knapsack where we minimize count instead of maximizing value. ```typescript function coinChange(coins: number[], amount: number): number { const dp = new Array(amount + 1).fill(Infinity); dp[0] = 0; for (const coin of coins) { for (let a = coin; a <= amount; a++) { dp[a] = Math.min(dp[a], dp[a - coin] + 1); } } return dp[amount] === Infinity ? -1 : dp[amount]; } ``` Notice the **forward iteration** on `a`. When computing `dp[a]`, `dp[a - coin]` may already include coin `coin` from this same iteration — that's exactly what we want, since coins are reusable. **Big O**: Time O(n × amount), Space O(amount). --- ### Coin Change II (LeetCode 518) — Count Combinations **Problem**: Given coin denominations and an amount, return the number of **combinations** that make up that amount. This is where **loop order becomes critical**. > **Combinations vs. Permutations**: If you loop `coins` in the outer loop and `amount` in the inner loop, you get **combinations** (each coin set is counted once). If you reverse the loop order, you get **permutations** (different orderings are counted separately). Why? When coins are in the outer loop, once you move past a coin, you never go back to it. Coin `[1, 2]` with amount 3: you count `{1,1,1}`, `{1,2}` — but never `{2,1}` separately. If amounts were outer, you'd consider all coins at every amount, counting order-dependent sequences. **Combinations (correct for this problem)**: ```typescript function change(amount: number, coins: number[]): number { const dp = new Array(amount + 1).fill(0); dp[0] = 1; for (const coin of coins) { for (let a = coin; a <= amount; a++) { dp[a] += dp[a - coin]; } } return dp[amount]; } ``` **If you wanted permutations** (like LC 377 Combination Sum IV): ```typescript function combinationSum4(nums: number[], target: number): number { const dp = new Array(target + 1).fill(0); dp[0] = 1; for (let t = 1; t <= target; t++) { for (const num of nums) { if (t >= num) { dp[t] += dp[t - num]; } } } return dp[target]; } ``` **Big O**: Time O(n × amount), Space O(amount) for both. --- ### Complete Knapsack Template Here's the general template for unbounded knapsack: ```typescript function unboundedKnapsack( weights: number[], values: number[], capacity: number ): number { const dp = new Array(capacity + 1).fill(0); for (let i = 0; i < weights.length; i++) { for (let w = weights[i]; w <= capacity; w++) { dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]); } } return dp[capacity]; } ``` Compare to 0/1 knapsack — the only difference is the inner loop direction: - **0/1 Knapsack**: `for (let w = capacity; w >= weights[i]; w--)` — reverse - **Unbounded Knapsack**: `for (let w = weights[i]; w <= capacity; w++)` — forward > **Unbounded Knapsack Takeaway**: Forward inner loop = items reusable. Loop order determines combinations vs. permutations. Memorize this — it comes up constantly in interviews and getting it wrong is a common trap. --- ## Pattern 4: Grid / Path DP Grid DP problems give you a 2D grid and ask you to find paths, minimum costs, or counts. The key: `dp[i][j]` depends on its neighbors — usually `dp[i-1][j]` (above) and `dp[i][j-1]` (left), sometimes `dp[i+1][j]` (below) when working bottom-up. --- ### Minimum Path Sum (LeetCode 64) **Problem**: Given an `m × n` grid of non-negative numbers, find a path from top-left to bottom-right that minimizes the sum. You can only move right or down. **The Recurrence**: `dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])` **Visual Walkthrough**: `grid = [[1,3,1],[1,5,1],[4,2,1]]` ``` Grid: DP Table: [ 1, 3, 1 ] [ 1, 4, 5 ] [ 1, 5, 1 ] → [ 2, 7, 6 ] [ 4, 2, 1 ] [ 6, 8, 7 ] ``` Answer: `dp[2][2] = 7`. Path: 1→3→1→1→1 = 7. Wait — actually the minimum is 1→1→4→2→1 = ... no. Let's trace: 1→1→5→1→1 = nope. The path is 1→3→1→1→1 = 7, going right-right-down-down. ```typescript function minPathSum(grid: number[][]): number { const m = grid.length; const n = grid[0].length; const dp: number[][] = Array.from({ length: m }, () => new Array(n).fill(0) ); dp[0][0] = grid[0][0]; for (let i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0]; for (let j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j]; for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]); } } return dp[m - 1][n - 1]; } ``` **Big O**: Time O(m × n), Space O(m × n) — can be done in-place by modifying `grid`. --- ### Unique Paths II (LeetCode 63) **Problem**: A robot starts at the top-left of an `m × n` grid and wants to reach the bottom-right. Some cells have obstacles (`1`). How many unique paths exist? **The Recurrence**: If `obstacleGrid[i][j] === 1`, `dp[i][j] = 0`. Otherwise, `dp[i][j] = dp[i-1][j] + dp[i][j-1]`. ```typescript function uniquePathsWithObstacles(obstacleGrid: number[][]): number { const m = obstacleGrid.length; const n = obstacleGrid[0].length; if (obstacleGrid[0][0] === 1 || obstacleGrid[m - 1][n - 1] === 1) return 0; const dp: number[][] = Array.from({ length: m }, () => new Array(n).fill(0) ); dp[0][0] = 1; for (let i = 1; i < m; i++) { dp[i][0] = obstacleGrid[i][0] === 1 ? 0 : dp[i - 1][0]; } for (let j = 1; j < n; j++) { dp[0][j] = obstacleGrid[0][j] === 1 ? 0 : dp[0][j - 1]; } for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; } ``` **Big O**: Time O(m × n), Space O(m × n). --- ### Triangle (LeetCode 120) **Problem**: Given a triangle array, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. **The Insight**: Work **bottom-up**. Start from the second-to-last row and pick the minimum of the two children. ``` [2] [11] [3,4] → [9, 10] [6,5,7] [7, 6, 10] [4,1,8,3] [4, 1, 8, 3] (base) ``` Answer: 11 (path: 2→3→5→1). ```typescript function minimumTotal(triangle: number[][]): number { const dp = [...triangle[triangle.length - 1]]; for (let row = triangle.length - 2; row >= 0; row--) { for (let col = 0; col <= row; col++) { dp[col] = triangle[row][col] + Math.min(dp[col], dp[col + 1]); } } return dp[0]; } ``` **Big O**: Time O(n²), Space O(n) where n = number of rows. --- ### Dungeon Game (LeetCode 174) **Problem**: A knight starts at the top-left of a dungeon grid and must reach the bottom-right. Each cell adds or removes HP. Find the minimum initial HP needed so the knight's HP never drops to 0 or below. **The Insight**: You must work **backwards** from the bottom-right. Why? Because the minimum HP at each cell depends on what's ahead, not what's behind. If a big health pack is coming, you can afford to be lower now. `dp[i][j]` = minimum HP needed when entering cell `(i, j)`. **Recurrence** (from bottom-right to top-left): - `dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])` - We need at least 1 HP at every point — you can't be dead. ```typescript function calculateMinimumHP(dungeon: number[][]): number { const m = dungeon.length; const n = dungeon[0].length; const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(Infinity) ); dp[m][n - 1] = 1; dp[m - 1][n] = 1; for (let i = m - 1; i >= 0; i--) { for (let j = n - 1; j >= 0; j--) { const minHpNeeded = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]; dp[i][j] = Math.max(minHpNeeded, 1); } } return dp[0][0]; } ``` **Big O**: Time O(m × n), Space O(m × n). > **Grid DP Takeaway**: Most grid problems go top-left → bottom-right. But some (like Dungeon Game) require **reverse DP** — start from the destination and work backwards. Always ask yourself: "which direction does the dependency flow?" --- ## Pattern 5: Interval DP Interval DP operates on **ranges** of an array. `dp[i][j]` represents the optimal answer for the subarray from index `i` to `j`. You typically iterate by **length** of the interval, building from small ranges to large. The canonical structure: ``` for length = 2 to n: for i = 0 to n - length: j = i + length - 1 for k = i to j - 1: // try all split points dp[i][j] = optimize(dp[i][k], dp[k+1][j], cost) ``` --- ### Burst Balloons (LeetCode 312) **Problem**: Given `n` balloons with numbers on them, bursting balloon `i` earns `nums[i-1] * nums[i] * nums[i+1]` coins. After bursting, the adjacent balloons become neighbors. Find the maximum coins. This is one of the trickiest DP problems. The key insight is counterintuitive. **The Insight**: Instead of thinking "which balloon to burst **first**," think "which balloon to burst **last** in the range `[i, j]`." If balloon `k` is the **last** to be burst in range `[i, j]`, then: - All balloons in `[i, k-1]` and `[k+1, j]` are already gone - The neighbors of `k` are `i-1` and `j+1` (the boundaries outside our range) - `dp[i][j] = max over all k of (dp[i][k-1] + dp[k+1][j] + nums[i-1] * nums[k] * nums[j+1])` We pad the array with `1` on both ends to handle boundaries. **Visual Walkthrough**: `nums = [3, 1, 5, 8]` → padded: `[1, 3, 1, 5, 8, 1]` Building up by interval length: ``` Length 1 (single balloons): dp[1][1]: burst 3 last → 1*3*1 = 3 dp[2][2]: burst 1 last → 3*1*5 = 15 dp[3][3]: burst 5 last → 1*5*8 = 40 dp[4][4]: burst 8 last → 5*8*1 = 40 Length 2: dp[1][2]: max(burst 3 last, burst 1 last) k=1: dp[2][2] + 1*3*5 = 15 + 15 = 30 k=2: dp[1][1] + 1*1*5 = 3 + 5 = 8 → dp[1][2] = 30 Length 4 (full range): dp[1][4] = 167 ``` Answer: 167. ```typescript function maxCoins(nums: number[]): number { const n = nums.length; const padded = [1, ...nums, 1]; const dp: number[][] = Array.from({ length: n + 2 }, () => new Array(n + 2).fill(0) ); for (let len = 1; len <= n; len++) { for (let i = 1; i <= n - len + 1; i++) { const j = i + len - 1; for (let k = i; k <= j; k++) { const coins = padded[i - 1] * padded[k] * padded[j + 1] + dp[i][k - 1] + dp[k + 1][j]; dp[i][j] = Math.max(dp[i][j], coins); } } } return dp[1][n]; } ``` **Big O**: Time O(n³), Space O(n²). --- ### Matrix Chain Multiplication **Problem**: Given dimensions of matrices, find the minimum number of scalar multiplications needed to compute their product. Same interval DP structure. `dp[i][j]` = minimum cost to multiply matrices `i` through `j`. Try every split point `k`: ```typescript function matrixChainMultiplication(dimensions: number[]): number { const n = dimensions.length - 1; const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0) ); for (let len = 2; len <= n; len++) { for (let i = 0; i <= n - len; i++) { const j = i + len - 1; dp[i][j] = Infinity; for (let k = i; k < j; k++) { const cost = dp[i][k] + dp[k + 1][j] + dimensions[i] * dimensions[k + 1] * dimensions[j + 1]; dp[i][j] = Math.min(dp[i][j], cost); } } } return dp[0][n - 1]; } ``` **Big O**: Time O(n³), Space O(n²). > **Interval DP Takeaway**: When the problem involves combining or splitting **ranges** optimally — think interval DP. The hallmark is a triple nested loop: length, start, split point. The "burst balloons" trick of thinking about what's done **last** is a classic technique. --- ## Pattern 6: State Machine DP State machine DP models problems where you transition between **states** at each step. Instead of a single DP value per position, you maintain **multiple values** — one for each state. The poster child: the **Best Time to Buy and Sell Stock** series. --- ### Stock I (LeetCode 121) — One Transaction **Problem**: You can buy once and sell once. Maximize profit. This doesn't even need DP — just track the minimum price seen so far. ```typescript function maxProfit1(prices: number[]): number { let minPrice = Infinity; let maxProfit = 0; for (const price of prices) { minPrice = Math.min(minPrice, price); maxProfit = Math.max(maxProfit, price - minPrice); } return maxProfit; } ``` **Big O**: Time O(n), Space O(1). --- ### Stock II (LeetCode 122) — Unlimited Transactions **Problem**: You can make as many transactions as you want (buy/sell pairs). No simultaneous holding. **State machine**: Two states — **holding** and **not holding**. ``` Not Holding ←——sell——→ Holding ↑ ↑ rest rest ``` ```typescript function maxProfit2(prices: number[]): number { let hold = -Infinity; let notHold = 0; for (const price of prices) { const prevHold = hold; const prevNotHold = notHold; hold = Math.max(prevHold, prevNotHold - price); notHold = Math.max(prevNotHold, prevHold + price); } return notHold; } ``` **Big O**: Time O(n), Space O(1). --- ### Stock III (LeetCode 123) — At Most 2 Transactions **Problem**: At most 2 buy-sell transactions. Maximize profit. **Four states**: `buy1`, `sell1`, `buy2`, `sell2` — representing the best profit at each stage. ``` start → buy1 → sell1 → buy2 → sell2 ``` ```typescript function maxProfit3(prices: number[]): number { let buy1 = -Infinity; let sell1 = 0; let buy2 = -Infinity; let sell2 = 0; for (const price of prices) { buy1 = Math.max(buy1, -price); sell1 = Math.max(sell1, buy1 + price); buy2 = Math.max(buy2, sell1 - price); sell2 = Math.max(sell2, buy2 + price); } return sell2; } ``` Why does this work? `buy1` tracks the cheapest buy. `sell1` tracks the best profit from one transaction. `buy2` effectively starts with the profit from the first transaction. `sell2` gives the total. **Big O**: Time O(n), Space O(1). --- ### Stock IV (LeetCode 188) — At Most k Transactions **Problem**: At most `k` buy-sell transactions. Maximize profit. Generalize Stock III. `dp[t][0]` = max profit after `t`-th buy, `dp[t][1]` = max profit after `t`-th sell. ```typescript function maxProfit4(k: number, prices: number[]): number { if (prices.length === 0 || k === 0) return 0; if (k >= Math.floor(prices.length / 2)) { let profit = 0; for (let i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) { profit += prices[i] - prices[i - 1]; } } return profit; } const buy = new Array(k + 1).fill(-Infinity); const sell = new Array(k + 1).fill(0); for (const price of prices) { for (let t = 1; t <= k; t++) { buy[t] = Math.max(buy[t], sell[t - 1] - price); sell[t] = Math.max(sell[t], buy[t] + price); } } return sell[k]; } ``` The `k >= prices.length / 2` check is an optimization: if you have enough transactions, it reduces to the unlimited case (Stock II). **Big O**: Time O(n × k), Space O(k). --- ### Stock with Cooldown (LeetCode 309) **Problem**: After selling, you must wait one day before buying again. Unlimited transactions. **Three states**: `hold`, `sold` (just sold today), `rest` (cooldown or idle). ``` rest ←—(wait)—— sold ↓ ↑ (buy) (sell) ↓ ↑ hold ——(sell)——→ sold ↑ (wait) ``` ```typescript function maxProfitCooldown(prices: number[]): number { let hold = -Infinity; let sold = 0; let rest = 0; for (const price of prices) { const prevHold = hold; const prevSold = sold; const prevRest = rest; hold = Math.max(prevHold, prevRest - price); sold = prevHold + price; rest = Math.max(prevRest, prevSold); } return Math.max(sold, rest); } ``` **Trace** with `prices = [1, 2, 3, 0, 2]`: ``` Day 0 (price=1): hold=-1, sold=0, rest=0 Day 1 (price=2): hold=-1, sold=1, rest=0 Day 2 (price=3): hold=-1, sold=2, rest=1 Day 3 (price=0): hold=1, sold=-1, rest=2 Day 4 (price=2): hold=1, sold=3, rest=2 ``` Answer: `max(sold=3, rest=2) = 3`. **Big O**: Time O(n), Space O(1). --- ### The General State Machine Framework For any stock-like problem (or really, any problem with states and transitions): 1. **Identify the states** — What distinct situations can you be in? (holding, not holding, cooldown, transaction count...) 2. **Define transitions** — From each state, what actions can you take, and where do they lead? 3. **Write the recurrence** — For each state at step `i`, compute the optimal value from the previous step's states 4. **Initialize** — Set starting values for each state (often `-Infinity` for impossible states, `0` for neutral) 5. **Return** — The answer is usually the max over the "done" states at the end ``` General template: for each day/step: for each state: newState[s] = best(transition from all valid previous states) ``` > **State Machine DP Takeaway**: When a problem has distinct phases or conditions that constrain your choices, model it as a state machine. The stock problems are the perfect training ground. Once you see the states and transitions, the code writes itself. --- ## Pattern 7: Longest Increasing Subsequence (LIS) Family The LIS pattern finds the longest subsequence where elements are strictly increasing (or some other order relation). It appears directly and as a building block in harder problems. --- ### LIS (LeetCode 300) — O(n²) DP **Problem**: Find the length of the longest strictly increasing subsequence. **The Recurrence**: `dp[i]` = length of the longest increasing subsequence ending at index `i`. For each `i`, look at all `j < i` where `nums[j] < nums[i]`: `dp[i] = max(dp[j] + 1)`. **Visual Walkthrough**: `nums = [10, 9, 2, 5, 3, 7, 101, 18]` ``` Index: 0 1 2 3 4 5 6 7 Value: 10 9 2 5 3 7 101 18 dp: 1 1 1 2 2 3 4 4 dp[3]=2: 2<5 → dp[2]+1 = 2 dp[5]=3: 2<7 → dp[2]+1=2, 5<7 → dp[3]+1=3, 3<7 → dp[4]+1=3 → max=3 dp[6]=4: ... 7<101 → dp[5]+1=4 dp[7]=4: ... 7<18 → dp[5]+1=4 ``` Answer: 4 (subsequence: `[2, 5, 7, 101]` or `[2, 3, 7, 101]` or `[2, 3, 7, 18]`). ```typescript function lengthOfLIS(nums: number[]): number { const n = nums.length; const dp = new Array(n).fill(1); for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } return Math.max(...dp); } ``` **Big O**: Time O(n²), Space O(n). --- ### LIS — O(n log n) with Binary Search (Patience Sorting) The O(n²) solution is fine for interviews, but the optimal O(n log n) approach uses a clever trick: maintain a **tails** array where `tails[i]` is the smallest tail element for an increasing subsequence of length `i + 1`. **The Idea**: For each number, either: - It's larger than all tails → append (extend LIS length) - Otherwise → find the leftmost tail that's ≥ this number and replace it (keep tails as small as possible for future extensions) The binary search finds the replacement position. **Walkthrough**: `nums = [10, 9, 2, 5, 3, 7, 101, 18]` ``` Process 10: tails = [10] Process 9: tails = [9] (replace 10, since 9 < 10) Process 2: tails = [2] (replace 9) Process 5: tails = [2, 5] (append) Process 3: tails = [2, 3] (replace 5) Process 7: tails = [2, 3, 7] (append) Process 101: tails = [2, 3, 7, 101] (append) Process 18: tails = [2, 3, 7, 18] (replace 101) ``` Length = `tails.length` = 4. Note: `tails` is NOT the actual LIS — it's just a tool for computing the length. ```typescript function lengthOfLISOptimal(nums: number[]): number { const tails: number[] = []; for (const num of nums) { let lo = 0; let hi = tails.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (tails[mid] < num) { lo = mid + 1; } else { hi = mid; } } tails[lo] = num; } return tails.length; } ``` **Big O**: Time O(n log n), Space O(n). --- ### Russian Doll Envelopes (LeetCode 354) **Problem**: Given envelopes with `[width, height]`, find the maximum number that can be nested (each must be strictly larger in both dimensions). **The LIS Connection**: Sort by width ascending. For envelopes with the same width, sort by height **descending**. Then find the LIS on heights. Why descending for same width? If two envelopes have the same width, you can't nest one inside the other. Sorting heights descending for same width ensures the LIS algorithm never picks two envelopes with the same width. ```typescript function maxEnvelopes(envelopes: number[][]): number { envelopes.sort((a, b) => { if (a[0] !== b[0]) return a[0] - b[0]; return b[1] - a[1]; }); const heights = envelopes.map(e => e[1]); return lengthOfLISOptimal(heights); } ``` **Big O**: Time O(n log n), Space O(n). --- ### Number of LIS (LeetCode 673) **Problem**: Find the number of longest increasing subsequences (not just the length, but the **count**). Maintain two arrays: `lengths[i]` and `counts[i]`. ```typescript function findNumberOfLIS(nums: number[]): number { const n = nums.length; const lengths = new Array(n).fill(1); const counts = new Array(n).fill(1); for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { if (nums[j] < nums[i]) { if (lengths[j] + 1 > lengths[i]) { lengths[i] = lengths[j] + 1; counts[i] = counts[j]; } else if (lengths[j] + 1 === lengths[i]) { counts[i] += counts[j]; } } } } const maxLen = Math.max(...lengths); let result = 0; for (let i = 0; i < n; i++) { if (lengths[i] === maxLen) { result += counts[i]; } } return result; } ``` **Big O**: Time O(n²), Space O(n). > **LIS Takeaway**: The O(n²) DP is straightforward. The O(n log n) patience sorting trick is worth knowing for optimal solutions and shows up in 2D variants like Russian Doll Envelopes. --- ## Pattern Recognition Guide Here's your mental flowchart for identifying which DP pattern applies. When you read a problem, look for these signals: | **Signal** | **Pattern** | **Template** | |---|---|---| | Two strings, subsequence/edit/match | String DP | 2D table, `dp[i][j]` on both strings | | Select items, max/min with constraint | 0/1 Knapsack | Take or skip, reverse inner loop | | Unlimited use of items | Unbounded Knapsack | Forward inner loop | | 2D grid, path from A to B | Grid/Path DP | `dp[i][j]` from neighbors | | Range/interval optimization | Interval DP | Triple loop: length, start, split | | States + transitions (buy/sell/hold) | State Machine DP | Multiple DP arrays per state | | Longest increasing order | LIS | `dp[i]` = best ending at `i`, binary search | | Circular array | Break the circle | Run twice with different boundaries | **When you're stuck**, ask these questions: 1. What are the **subproblems**? (What smaller version of this problem can I solve?) 2. What are the **choices** at each step? (Take/skip, go left/right, match/don't match?) 3. What **dimensions** do I need? (One string → 1D, two strings → 2D, items + capacity → 2D) 4. What's the **base case**? (Empty string, zero items, reached the destination?) 5. Which **direction** do dependencies flow? (Usually top-left → bottom-right, but sometimes reverse) --- ## Advanced Techniques (Brief Intros) These are patterns you'll encounter in hard problems and competitive programming. They're worth knowing about even if you don't need them for most interviews. --- ### Bitmask DP When the state space involves a **subset of items** (e.g., which cities have been visited), represent the subset as a bitmask. `dp[mask]` gives the answer for the subset encoded by `mask`. **Classic Problem**: Traveling Salesman Problem — visit all cities exactly once with minimum cost. ```typescript function tsp(dist: number[][]): number { const n = dist.length; const ALL_VISITED = (1 << n) - 1; const dp: number[][] = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity) ); dp[1][0] = 0; for (let mask = 1; mask <= ALL_VISITED; mask++) { for (let u = 0; u < n; u++) { if (dp[mask][u] === Infinity) continue; if (!(mask & (1 << u))) continue; for (let v = 0; v < n; v++) { if (mask & (1 << v)) continue; const newMask = mask | (1 << v); dp[newMask][v] = Math.min( dp[newMask][v], dp[mask][u] + dist[u][v] ); } } } let result = Infinity; for (let u = 0; u < n; u++) { result = Math.min(result, dp[ALL_VISITED][u] + dist[u][0]); } return result; } ``` **Big O**: Time O(2ⁿ × n²), Space O(2ⁿ × n). Only feasible for `n ≤ ~20`. > Bitmask DP is a brute-force over subsets — but it's smart brute-force. When n is small and the state involves "which elements have been used," reach for bitmasks. --- ### Digit DP Used for counting numbers in a range `[L, R]` that satisfy some property (e.g., digit sum equals K, no repeated digits). You build numbers digit by digit, tracking whether you're still "tight" against the upper bound. The state typically includes: current position, some accumulated property, and a `tight` flag indicating if previous digits matched the upper bound exactly. This is niche but appears in competitive programming and occasionally in hard interview problems. The key idea: `count(0, R) - count(0, L-1)` gives you the count in range `[L, R]`. --- ### DP on Trees When the DP is defined on a tree structure rather than an array or grid. Each node's DP value depends on its children. **Classic Problem**: Maximum independent set on a tree — select nodes with maximum total weight such that no two selected nodes are adjacent. ```typescript function maxIndependentSet( adj: number[][], weights: number[] ): number { const n = weights.length; const include = new Array(n).fill(0); const exclude = new Array(n).fill(0); const visited = new Array(n).fill(false); function dfs(node: number): void { visited[node] = true; include[node] = weights[node]; exclude[node] = 0; for (const child of adj[node]) { if (visited[child]) continue; dfs(child); include[node] += exclude[child]; exclude[node] += Math.max(include[child], exclude[child]); } } dfs(0); return Math.max(include[0], exclude[0]); } ``` **Big O**: Time O(n), Space O(n). > Tree DP follows a natural post-order traversal: solve children first, then combine at the parent. It's DFS + DP combined. --- ## Common Pitfalls These are the mistakes that will cost you an interview if you're not careful. Every one of these has burned someone. ### 1. Wrong Loop Order in Knapsack The number one knapsack mistake. Remember: - **0/1 Knapsack** (each item once): inner loop goes **high to low** - **Unbounded Knapsack** (unlimited items): inner loop goes **low to high** - **Combinations**: items in outer loop - **Permutations**: target in outer loop Getting this wrong gives you a solution that silently produces incorrect results. No runtime error, no crash — just wrong answers. Extremely dangerous. ### 2. Forgetting Empty String Base Cases In string DP, row 0 and column 0 represent the **empty string**. Forgetting to initialize them correctly is a classic off-by-one error. - Edit Distance: `dp[i][0] = i`, `dp[0][j] = j` - Distinct Subsequences: `dp[i][0] = 1` - LCS: `dp[i][0] = 0`, `dp[0][j] = 0` Always ask: "What's the answer when one or both strings are empty?" ### 3. Incorrect Interval Boundaries In interval DP, off-by-one errors with `i`, `j`, and `k` are rampant. Double-check: - Is your range inclusive on both ends? - Does `k` range from `i` to `j-1` or `i` to `j`? - Are you indexing into the original array or the padded array? ### 4. Not Copying State in Backtracking/Counting When collecting results (like in Target Sum or counting subsequences), make sure you're not accidentally sharing mutable state. Use `[...array]` to copy arrays when storing results. ### 5. Integer Overflow in Counting Problems JavaScript/TypeScript numbers can lose precision at very large values. For problems that ask you to return the answer modulo `10⁹ + 7`, apply the modulo at every addition step: ```typescript dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % (1e9 + 7); ``` ### 6. Space Optimization Breaking Logic When optimizing from 2D to 1D, you need to be extra careful about which values you're reading. In 0/1 knapsack, the reverse loop ensures you read "previous row" values. If you accidentally use a value that's already been updated in this iteration, you've broken the recurrence. **Pro tip**: Get the 2D version working first. Only optimize space after the logic is correct and tested. ### 7. Not Recognizing the Pattern The biggest pitfall isn't a coding bug — it's staring at a problem for 20 minutes without recognizing which pattern it belongs to. Use the pattern recognition guide above. Read the problem statement for keywords: "subsequence" (string DP or LIS), "subset" (knapsack), "grid/path" (path DP), "buy and sell" (state machine), "range/interval" (interval DP). --- ## Cheat Sheet ### String DP ```typescript // Template: Two strings → 2D table // dp[i][j] = answer for text1[0..i-1], text2[0..j-1] for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (text1[i-1] === text2[j-1]) { dp[i][j] = /* match case */; } else { dp[i][j] = /* no match case */; } } } ``` | Problem | Match | No Match | |---|---|---| | LCS | `dp[i-1][j-1] + 1` | `max(dp[i-1][j], dp[i][j-1])` | | Edit Distance | `dp[i-1][j-1]` | `1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])` | | Distinct Subseq | `dp[i-1][j-1] + dp[i-1][j]` | `dp[i-1][j]` | ### 0/1 Knapsack ```typescript // 1D optimization — REVERSE inner loop for (const item of items) { for (let w = capacity; w >= item.weight; w--) { dp[w] = Math.max(dp[w], dp[w - item.weight] + item.value); } } ``` ### Unbounded Knapsack ```typescript // 1D — FORWARD inner loop for (const item of items) { for (let w = item.weight; w <= capacity; w++) { dp[w] = Math.max(dp[w], dp[w - item.weight] + item.value); } } ``` ### Grid Path DP ```typescript // Standard: top-left → bottom-right dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]); // Reverse: bottom-right → top-left (Dungeon Game) dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - grid[i][j]); ``` ### Interval DP ```typescript for (let len = 2; len <= n; len++) { for (let i = 0; i <= n - len; i++) { const j = i + len - 1; for (let k = i; k < j; k++) { dp[i][j] = optimize(dp[i][k] + dp[k+1][j] + cost(i, k, j)); } } } ``` ### State Machine DP (Stock Template) ```typescript // States: hold, notHold (+ optional: cooldown, transaction count) for (const price of prices) { newHold = max(hold, notHold - price); // buy or keep holding newNotHold = max(notHold, hold + price); // sell or keep idle } ``` ### LIS ```typescript // O(n²) for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1); } } // O(n log n) — patience sorting for (const num of nums) { const pos = lowerBound(tails, num); tails[pos] = num; // replace or append } ``` ### Big O Reference | Pattern | Time | Space | |---|---|---| | String DP (2 strings) | O(m × n) | O(m × n) or O(n) | | 0/1 Knapsack | O(n × W) | O(W) | | Unbounded Knapsack | O(n × W) | O(W) | | Grid Path | O(m × n) | O(m × n) or O(n) | | Interval DP | O(n³) | O(n²) | | State Machine (stocks) | O(n × k) | O(k) | | LIS (DP) | O(n²) | O(n) | | LIS (Binary Search) | O(n log n) | O(n) | | Bitmask DP | O(2ⁿ × n²) | O(2ⁿ × n) | --- ## Wrapping Up Dynamic programming isn't about memorizing solutions — it's about recognizing shapes. Every problem in this guide reduces to the same core idea: **define subproblems, find the recurrence, build up the answer**. What changes from problem to problem is the *shape* of the subproblems. Here's what you should take away: 1. **String DP**: Two strings, 2D table, compare characters. LCS is the prototype. 2. **Knapsack (0/1)**: Take or skip with a constraint. Reverse inner loop. Everything is a knapsack variant if you squint hard enough. 3. **Knapsack (Unbounded)**: Same but forward inner loop. Loop order determines combinations vs. permutations. 4. **Grid DP**: Your dp table IS the grid. Dependencies flow from neighbors. 5. **Interval DP**: Optimize over ranges. Triple loop. Think about what happens *last*. 6. **State Machine DP**: Multiple states, transitions between them. The stock problems are your training ground. 7. **LIS**: Longest increasing order. O(n²) DP or O(n log n) with binary search. The problems in this guide are the problems. If you can solve these confidently, you can handle the vast majority of DP questions in interviews. Practice them until the patterns are automatic — not memorized, but *recognized*. > "DP problems aren't solved by cleverness. They're solved by someone who's seen the pattern before and knows which tool to reach for." Now go build that muscle memory. Pick a pattern, solve 3–5 problems in it, then move to the next. Your future interviewing self will thank you.

Problem Solving Patterns: Dynamic Programming, Made Simple