7a:T434,Interval DP is a specialized dynamic programming pattern where the **state is defined by the boundaries of a contiguous subinterval** within the input. Unlike 1D DP where state might be a single index `dp[i]`, or 2D DP with independent indices `dp[i][j]`, Interval DP uses `dp[i][j]` where `i` and `j` represent the **left and right boundaries** of a subinterval, and `i ≤ j`. **The Defining Characteristics:** 1. **Contiguity**: The subproblem is always a contiguous portion of the original input—never scattered elements. 2. **Boundary Representation**: State `dp[i][j]` represents the optimal solution for elements from index `i` to index `j` (inclusive or exclusive, depending on convention). 3. **Combining Subintervals**: The solution for interval `[i, j]` is computed by trying all possible **split points** `k` where `i ≤ k < j`, combining solutions for `[i, k]` and `[k+1, j]`. 4. **Bottom-Up by Length**: In tabulation, intervals are processed in order of increasing length—first length 1, then length 2, and so on—ensuring dependencies are satisfied.7b:T55b,The Matrix Chain Multiplication (MCM) problem is the most famous Interval DP problem, serving as the canonical introduction to this pattern. Let's dissect it completely. **Problem Statement:** Given a chain of `n` matrices `A₁, A₂, ..., Aₙ`, where matrix `Aᵢ` has dimensions `p[i-1] × p[i]`, find the minimum number of scalar multiplications required to compute the product `A₁ × A₂ × ... × Aₙ`. **Key Insight: Associativity Without Commutativity** Matrix multiplication is: - **Associative**: `(A × B) × C = A × (B × C)` — same result - **Not commutative**: `A × B ≠ B × A` in general The associative property means we can parenthesize in any way without changing the result. But the computational cost varies wildly: **Example:** Consider three matrices: - `A₁`: 10 × 100 - `A₂`: 100 × 5 - `A₃`: 5 × 50 Multiplying `(A₁ × A₂)` first: - `A₁ × A₂` costs 10 × 100 × 5 = 5,000 operations → result is 10 × 5 - Then × `A₃` costs 10 × 5 × 50 = 2,500 operations - **Total: 7,500 operations** Multiplying `(A₂ × A₃)` first: - `A₂ × A₃` costs 100 × 5 × 50 = 25,000 operations → result is 100 × 50 - Then `A₁ ×` result costs 10 × 100 × 50 = 50,000 operations - **Total: 75,000 operations** The first ordering is **10× more efficient**! For longer chains, the difference can be exponential.7c:Tb64,def matrix_chain_order(p: list[int]) -> int: """ Find minimum number of scalar multiplications to multiply a chain of matrices with dimensions given by p. Matrix i has dimensions p[i-1] x p[i]. So for n matrices, p has n+1 elements. Returns: Minimum number of scalar multiplications. Time Complexity: O(n³) Space Complexity: O(n²) """ n = len(p) - 1 # Number of matrices if n == 0: return 0 # dp[i][j] = min cost to multiply matrices i through j (1-indexed) # We'll use 1-indexed for matrices, so dp size is (n+1) x (n+1) dp = [[0] * (n + 1) for _ in range(n + 1)] # Base case: single matrix costs 0 # dp[i][i] = 0 (already initialized) # Fill by increasing chain length for length in range(2, n + 1): # length of chain for i in range(1, n - length + 2): # start of chain j = i + length - 1 # end of chain dp[i][j] = float('inf') # Try all split points for k in range(i, j): # Cost = cost of left part + cost of right part + cost of final multiplication cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j] dp[i][j] = min(dp[i][j], cost) return dp[1][n] def matrix_chain_with_solution(p: list[int]) -> tuple[int, str]: """ Extended version that also returns the optimal parenthesization. """ n = len(p) - 1 if n == 0: return 0, "" if n == 1: return 0, "A1" dp = [[0] * (n + 1) for _ in range(n + 1)] split = [[0] * (n + 1) for _ in range(n + 1)] # Records where to split for length in range(2, n + 1): for i in range(1, n - length + 2): j = i + length - 1 dp[i][j] = float('inf') for k in range(i, j): cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j] if cost < dp[i][j]: dp[i][j] = cost split[i][j] = k # Remember the optimal split point def build_solution(i: int, j: int) -> str: if i == j: return f"A{i}" k = split[i][j] left = build_solution(i, k) right = build_solution(k + 1, j) return f"({left} × {right})" return dp[1][n], build_solution(1, n) # Example usage if __name__ == "__main__": # Dimensions: A1 is 10x100, A2 is 100x5, A3 is 5x50 dimensions = [10, 100, 5, 50] min_cost = matrix_chain_order(dimensions) print(f"Minimum multiplications: {min_cost}") min_cost, parenthesization = matrix_chain_with_solution(dimensions) print(f"Optimal parenthesization: {parenthesization}") print(f"Total cost: {min_cost}") # Output: # Minimum multiplications: 7500 # Optimal parenthesization: ((A1 × A2) × A3) # Total cost: 75007d:Ta38,function matrixChainOrder(p: number[]): number { /** * Find minimum number of scalar multiplications to multiply * a chain of matrices with dimensions given by p. * * Matrix i has dimensions p[i-1] x p[i]. * So for n matrices, p has n+1 elements. * * Time Complexity: O(n³) * Space Complexity: O(n²) */ const n = p.length - 1; // Number of matrices if (n === 0) return 0; // dp[i][j] = min cost to multiply matrices i through j (1-indexed) const dp: number[][] = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0) ); // Fill by increasing chain length for (let length = 2; length <= n; length++) { for (let i = 1; i <= n - length + 1; i++) { const j = i + length - 1; dp[i][j] = Infinity; // Try all split points for (let k = i; k < j; k++) { const cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]; dp[i][j] = Math.min(dp[i][j], cost); } } } return dp[1][n]; } function matrixChainWithSolution(p: number[]): [number, string] { /** * Extended version that also returns the optimal parenthesization. */ const n = p.length - 1; if (n === 0) return [0, ""]; if (n === 1) return [0, "A1"]; const dp: number[][] = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0) ); const split: number[][] = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0) ); for (let length = 2; length <= n; length++) { for (let i = 1; i <= n - length + 1; i++) { const j = i + length - 1; dp[i][j] = Infinity; for (let k = i; k < j; k++) { const cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]; if (cost < dp[i][j]) { dp[i][j] = cost; split[i][j] = k; } } } } function buildSolution(i: number, j: number): string { if (i === j) return `A${i}`; const k = split[i][j]; return `(${buildSolution(i, k)} × ${buildSolution(k + 1, j)})`; } return [dp[1][n], buildSolution(1, n)]; } // Example usage const dimensions = [10, 100, 5, 50]; console.log(`Minimum multiplications: ${matrixChainOrder(dimensions)}`); const [minCost, parenthesization] = matrixChainWithSolution(dimensions); console.log(`Optimal parenthesization: ${parenthesization}`); console.log(`Total cost: ${minCost}`);7e:T466,The Burst Balloons problem (LeetCode 312) is a masterclass in recognizing interval DP when it's not immediately obvious. It also demonstrates a crucial technique: **thinking in reverse**. **Problem Statement:** You have `n` balloons, indexed from `0` to `n-1`. Each balloon is painted with a number represented by array `nums`. You are asked to burst all balloons. If you burst balloon `i`, you will get `nums[i-1] × nums[i] × nums[i+1]` coins. After the burst, `i-1` and `i+1` become adjacent. Find the maximum coins you can collect. **Note:** `nums[-1] = nums[n] = 1` (virtual boundaries). **Example:** - `nums = [3, 1, 5, 8]` - Optimal order: Burst 1 → 5 → 3 → 8 - Coins: 3×1×5 + 3×5×8 + 1×3×8 + 1×8×1 = 15 + 120 + 24 + 8 = 167 **Why Is This Hard?** The naive approach thinks *forward*: 'Which balloon should I burst first?' But here's the problem—when you burst a balloon, the adjacencies change! The coin value for bursting balloon `i` depends on which neighbors are still present, which depends on the entire history of bursts. This seems to require tracking the full state of remaining balloons.7f:Tc71,def max_coins(nums: list[int]) -> int: """ Find maximum coins by bursting all balloons optimally. Key insight: Think backwards - which balloon is burst LAST in each interval? Time Complexity: O(n³) Space Complexity: O(n²) """ # Add virtual balloons at boundaries balloons = [1] + nums + [1] n = len(balloons) # dp[i][j] = max coins from bursting all balloons in open interval (i, j) # Balloons i and j are boundaries, not to be burst in this subproblem dp = [[0] * n for _ in range(n)] # Process by interval length for length in range(2, n): # length from 2 to n-1 for i in range(n - length): j = i + length # Try each balloon k in (i, j) as the LAST one to burst for k in range(i + 1, j): # Coins from left, right, and bursting k last coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j] dp[i][j] = max(dp[i][j], coins) # Answer is for interval (0, n-1), which is the entire original array return dp[0][n - 1] def max_coins_with_order(nums: list[int]) -> tuple[int, list[int]]: """ Extended version that also returns the optimal burst order. """ balloons = [1] + nums + [1] n = len(balloons) dp = [[0] * n for _ in range(n)] last = [[0] * n for _ in range(n)] # Which balloon is burst last in (i, j) for length in range(2, n): for i in range(n - length): j = i + length for k in range(i + 1, j): coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j] if coins > dp[i][j]: dp[i][j] = coins last[i][j] = k def reconstruct(i: int, j: int) -> list[int]: """Reconstruct burst order from the 'last' table.""" if j <= i + 1: return [] k = last[i][j] # First burst everything except k left_order = reconstruct(i, k) right_order = reconstruct(k, j) # Then burst k (converted back to 0-indexed original) return left_order + right_order + [k - 1] # k-1 because we added boundary order = reconstruct(0, n - 1) return dp[0][n - 1], order # Example if __name__ == "__main__": nums = [3, 1, 5, 8] max_coins_value = max_coins(nums) print(f"Maximum coins: {max_coins_value}") max_coins_value, burst_order = max_coins_with_order(nums) print(f"Maximum coins: {max_coins_value}") print(f"Burst order (0-indexed): {burst_order}") # Verify: simulate the burst order remaining = list(nums) total = 0 for idx in burst_order: # Find actual position after previous bursts left = remaining[idx - 1] if idx > 0 else 1 right = remaining[idx + 1] if idx < len(remaining) - 1 else 1 coins = left * remaining[idx] * right total += coins print(f" Burst balloon {remaining[idx]} at position {idx}: {left}×{remaining[idx]}×{right} = {coins}") remaining.pop(idx) print(f"Total verified: {total}")80:T98b,function maxCoins(nums: number[]): number { /** * Find maximum coins by bursting all balloons optimally. * * Key insight: Think backwards - which balloon is burst LAST in each interval? * * Time Complexity: O(n³) * Space Complexity: O(n²) */ // Add virtual balloons at boundaries const balloons = [1, ...nums, 1]; const n = balloons.length; // dp[i][j] = max coins from bursting all balloons in open interval (i, j) const dp: number[][] = Array.from({ length: n }, () => Array(n).fill(0)); // Process by interval length for (let length = 2; length < n; length++) { for (let i = 0; i < n - length; i++) { const j = i + length; // Try each balloon k in (i, j) as the LAST one to burst for (let k = i + 1; k < j; k++) { const coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j]; dp[i][j] = Math.max(dp[i][j], coins); } } } return dp[0][n - 1]; } function maxCoinsWithOrder(nums: number[]): [number, number[]] { /** * Extended version that also returns the optimal burst order. */ const balloons = [1, ...nums, 1]; const n = balloons.length; const dp: number[][] = Array.from({ length: n }, () => Array(n).fill(0)); const last: number[][] = Array.from({ length: n }, () => Array(n).fill(0)); for (let length = 2; length < n; length++) { for (let i = 0; i < n - length; i++) { const j = i + length; for (let k = i + 1; k < j; k++) { const coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j]; if (coins > dp[i][j]) { dp[i][j] = coins; last[i][j] = k; } } } } function reconstruct(i: number, j: number): number[] { if (j <= i + 1) return []; const k = last[i][j]; return [...reconstruct(i, k), ...reconstruct(k, j), k - 1]; } return [dp[0][n - 1], reconstruct(0, n - 1)]; } // Example const nums = [3, 1, 5, 8]; console.log(`Maximum coins: ${maxCoins(nums)}`); const [maxVal, order] = maxCoinsWithOrder(nums); console.log(`Maximum coins: ${maxVal}`); console.log(`Burst order: ${order}`);81:T555,The Optimal Binary Search Tree (OBST) problem extends interval DP to tree construction. Given a sorted sequence of keys with known access frequencies, we want to build a BST that minimizes the expected search cost. **Problem Statement:** Given `n` sorted keys `k₁ < k₂ < ... < kₙ` with access probabilities `p[1], p[2], ..., p[n]`, find the BST that minimizes: ``` Expected Cost = Σ (depth(kᵢ) + 1) × p[i] = Σ (level of kᵢ) × p[i] ``` Where level of root = 1, and each child is one level deeper. **Why Interval DP?** When we choose key `kᵣ` as the root of a subtree containing keys `kᵢ` to `kⱼ`: - Keys `kᵢ, kᵢ₊₁, ..., kᵣ₋₁` go to the left subtree - Keys `kᵣ₊₁, kᵣ₊₂, ..., kⱼ` go to the right subtree Both subtrees are **contiguous intervals** of the original sorted sequence! This is the hallmark of interval DP. **The Recurrence:** Let `dp[i][j]` = minimum expected cost for a BST containing keys `kᵢ` to `kⱼ`. Let `w[i][j]` = sum of probabilities `p[i] + p[i+1] + ... + p[j]`. **Base Case:** - `dp[i][i] = p[i]` (single key tree) - `dp[i][i-1] = 0` (empty tree, for convenience) **Recurrence:** ``` dp[i][j] = w[i][j] + min over r ∈ [i, j] { dp[i][r-1] + dp[r+1][j] } ``` The `w[i][j]` term accounts for all keys in the subtree going one level deeper when attached under a root.82:Tc1c,def optimal_bst(keys: list, prob: list[float]) -> tuple[float, list[list[int]]]: """ Find the optimal BST minimizing expected search cost. Args: keys: Sorted list of keys prob: prob[i] = access probability of keys[i] Returns: Tuple of (minimum expected cost, root table for reconstruction) Time Complexity: O(n³) - can be optimized to O(n²) using Knuth's optimization Space Complexity: O(n²) """ n = len(keys) if n == 0: return 0.0, [] # Precompute prefix sums for O(1) range sum queries prefix_sum = [0.0] * (n + 1) for i in range(n): prefix_sum[i + 1] = prefix_sum[i] + prob[i] def weight(i: int, j: int) -> float: """Sum of probabilities from index i to j (0-indexed, inclusive).""" if i > j: return 0.0 return prefix_sum[j + 1] - prefix_sum[i] # dp[i][j] = min expected cost for keys[i..j] # Using n+2 size to handle boundary cases elegantly dp = [[0.0] * (n + 1) for _ in range(n + 2)] root = [[0] * (n + 1) for _ in range(n + 2)] # Base case: single keys for i in range(n): dp[i][i] = prob[i] root[i][i] = i # Fill by increasing length for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 dp[i][j] = float('inf') w = weight(i, j) # Try each key as root for r in range(i, j + 1): # Cost of left subtree (if exists) left_cost = dp[i][r - 1] if r > i else 0.0 # Cost of right subtree (if exists) right_cost = dp[r + 1][j] if r < j else 0.0 cost = w + left_cost + right_cost if cost < dp[i][j]: dp[i][j] = cost root[i][j] = r return dp[0][n - 1], root def print_optimal_bst(keys: list, root: list[list[int]], i: int, j: int, parent: str = "", direction: str = "Root"): """Recursively print the structure of the optimal BST.""" if i > j: return r = root[i][j] if parent: print(f" {keys[r]} is {direction} child of {parent}") else: print(f" {keys[r]} is the Root") print_optimal_bst(keys, root, i, r - 1, keys[r], "left") print_optimal_bst(keys, root, r + 1, j, keys[r], "right") # Example if __name__ == "__main__": # Keys and their access frequencies keys = ['A', 'B', 'C', 'D', 'E'] probabilities = [0.25, 0.20, 0.05, 0.20, 0.30] # Must sum to 1 min_cost, root_table = optimal_bst(keys, probabilities) print(f"Keys: {keys}") print(f"Probabilities: {probabilities}") print(f"Minimum expected search cost: {min_cost:.4f}") print(f" Optimal BST structure:") print_optimal_bst(keys, root_table, 0, len(keys) - 1) # The optimal BST might look quite different from a balanced tree # because frequently accessed keys should be near the root72:{"json":{"id":"seed_25dbaceeb56308e7ef1629ccacfca9c2","slug":"common-dp-patterns","category":"Data Structures & Algorithms","topic":"Common DP Patterns","title":"Common DP Patterns","description":"Master advanced dynamic programming patterns including Interval DP, Bitmask DP, DP on Trees, and DP with multiple constraints. These patterns extend the foundational DP techniques to solve sophisticated optimization problems across diverse domains.","difficulty":"ADVANCED","estimatedMinutes":90,"pages":[{"id":"seed_4d816f31b7a584bf81437bc227b458e4","title":"Interval DP","order":0,"content":[{"id":"interval-dp-intro","title":"The Art of Dividing and Conquering Intervals","content":[{"data":{"content":"Consider a seemingly simple question: given a sequence of matrices, what is the minimum number of scalar multiplications needed to compute their product? At first glance, you might think—just multiply them left to right. But matrix multiplication is associative, meaning the final result is the same regardless of how you parenthesize the expression. The *cost*, however, can vary dramatically depending on the order of operations.\n\nThis observation opens the door to one of the most elegant patterns in dynamic programming: **Interval DP**. In this paradigm, the state represents a *contiguous subinterval* of the input, and the solution for larger intervals is built by combining solutions from smaller, contained intervals. It's a pattern that appears across an astonishing variety of problems—from optimal parenthesization to game theory, from computational geometry to bioinformatics."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will:\n\n• Understand the structural signature of Interval DP problems\n• Master the canonical Matrix Chain Multiplication problem\n• Solve the Burst Balloons problem using interval thinking\n• Recognize when O(n³) complexity is acceptable and optimal\n• Implement interval DP with both memoization and tabulation\n• Develop intuition for placing the 'split point' in interval problems","variant":"info"},"type":"callout"}]},{"id":"understanding-interval-dp","title":"Understanding Interval DP","content":[{"data":{"content":"$7a"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Split Point Intuition","content":"Think of every interval problem as asking: 'Where should I make the final cut?' or 'What is the last operation performed on this interval?' The split point k represents this critical decision. By trying all possible split points, we exhaustively explore all ways to decompose the problem.","variant":"note"},"type":"callout"},{"data":{"content":"**The General Recurrence Pattern:**\n\nFor most interval DP problems, the recurrence follows this template:\n\n```\ndp[i][j] = optimize over k in [i, j-1] {\n dp[i][k] ⊕ dp[k+1][j] ⊕ cost(i, k, j)\n}\n```\n\nWhere:\n- `optimize` is typically min or max\n- `⊕` represents problem-specific combination (often addition)\n- `cost(i, k, j)` is the cost of combining the two sub-solutions at split point `k`\n\n**Base Cases:**\n\n- Single-element intervals `dp[i][i]` often have trivial optimal values (0 cost, no operation needed)\n- Empty intervals may or may not be meaningful depending on the problem"},"type":"text"},{"data":{"rows":[["State Meaning","Position i","Positions (i, j) in grid","Subinterval [i, j]"],["Typical Dimensions","O(n)","O(m × n)","O(n²) upper triangle"],["Dependencies","Previous indices","Adjacent cells","All contained intervals"],["Fill Order","Left to right","Row by row or diagonal","By interval length"],["Time Complexity","O(n)","O(m × n)","O(n²) to O(n³)"],["Example Problems","Fibonacci, House Robber","Grid Paths, LCS","MCM, Burst Balloons"]],"caption":"Interval DP vs Other DP Patterns","headers":["Characteristic","1D DP","2D Grid DP","Interval DP"]},"type":"table"}],"titleType":"number","titleNumber":1},{"id":"matrix-chain-multiplication","title":"Matrix Chain Multiplication — The Canonical Example","content":[{"data":{"content":"$7b"},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Exponential Search Space","content":"The number of ways to parenthesize n matrices is the (n-1)th Catalan number: C(n-1) = (2n-2)! / (n!(n-1)!). For n=10, there are 4,862 ways. For n=20, over 1.7 billion. Brute force is utterly infeasible; DP reduces this to O(n³).","variant":"warning"},"type":"callout"},{"data":{"content":"**Formulating the DP:**\n\nLet `dp[i][j]` = minimum cost to multiply matrices from `Aᵢ` to `Aⱼ`.\n\n**Base Case:**\n- `dp[i][i] = 0` — a single matrix requires no multiplication.\n\n**Recurrence:**\n\nFor the subchain from `i` to `j`, we try every possible split point `k` where we compute `Aᵢ...Aₖ` separately from `Aₖ₊₁...Aⱼ`, then multiply the results:\n\n```\ndp[i][j] = min over k ∈ [i, j-1] {\n dp[i][k] + dp[k+1][j] + p[i-1] × p[k] × p[j]\n}\n```\n\nThe term `p[i-1] × p[k] × p[j]` is the cost of the final multiplication:\n- Left subproduct has dimensions `p[i-1] × p[k]`\n- Right subproduct has dimensions `p[k] × p[j]`\n- Multiplying them costs `p[i-1] × p[k] × p[j]`\n\n**Why This Works:**\n\nAny valid parenthesization has a **last multiplication** that splits the chain into two parts. By trying all possible positions for this last multiplication and recursing on both parts, we explore all parenthesizations."},"type":"text"},{"data":{"fileName":"matrix_chain_multiplication.py","languages":[{"code":"$7c","label":"Python","value":"python"},{"code":"$7d","label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":2},{"id":"burst-balloons","title":"Burst Balloons — Interval DP in Disguise","content":[{"data":{"content":"$7e"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Key Insight: Think Backwards","content":"Instead of asking 'Which balloon do I burst FIRST in this interval?', ask 'Which balloon do I burst LAST?' If balloon k is the LAST to be burst in interval (i, j), then when we burst k, all other balloons in (i, j) are already gone. The neighbors of k are exactly i and j! This eliminates the dependency on burst history.","variant":"tip"},"type":"callout"},{"data":{"content":"**Reformulating with Interval DP:**\n\nLet `dp[i][j]` = maximum coins obtainable by bursting all balloons in the **open interval** `(i, j)`, assuming balloons at positions `i` and `j` are **not burst** (they serve as boundaries).\n\nWe add virtual balloons: `nums[-1] = 1` and `nums[n] = 1`.\n\n**Base Case:**\n- `dp[i][j] = 0` when `j ≤ i + 1` (no balloons between i and j)\n\n**Recurrence:**\n\nFor interval `(i, j)`, try each balloon `k` in `(i, j)` as the **last** balloon to burst:\n\n```\ndp[i][j] = max over k ∈ (i+1, ..., j-1) {\n dp[i][k] + dp[k][j] + nums[i] × nums[k] × nums[j]\n}\n```\n\n**Understanding the Recurrence:**\n\n- `dp[i][k]`: Maximum coins from bursting all balloons in `(i, k)` (before k)\n- `dp[k][j]`: Maximum coins from bursting all balloons in `(k, j)` (before k)\n- `nums[i] × nums[k] × nums[j]`: Coins when k is finally burst (neighbors are i and j, since everything else between i and j is gone)\n\nThe \"reverse thinking\" transforms a problem with complex state dependencies into clean interval DP!"},"type":"text"},{"data":{"fileName":"burst_balloons.py","languages":[{"code":"$7f","label":"Python","value":"python"},{"code":"$80","label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"optimal-bst","title":"Optimal Binary Search Tree — Interval DP for Tree Construction","content":[{"data":{"content":"$81"},"type":"text"},{"data":{"icon":"Info","title":"The Weight Term Explained","content":"When we make kᵣ the root, all other keys in [i, j] become one level deeper. This adds w[i][j] - p[r] to the cost. But we also count p[r] for the root itself at level 1. Combined with the recursive costs (which already count depths relative to subtree roots), we get the elegant formula: cost = w[i][j] + cost(left subtree) + cost(right subtree).","variant":"note"},"type":"callout"},{"data":{"fileName":"optimal_bst.py","languages":[{"code":"$82","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":4},{"id":"common-patterns-variations","title":"Common Patterns and Problem Variations","content":[{"data":{"content":"Interval DP problems share recognizable signatures. Learning to spot these patterns accelerates your problem-solving ability."},"type":"text"},{"data":{"items":["**Sequential Operations on Arrays**: Problems where you perform operations on a sequence and the operation's effect depends on neighbors or boundaries.","**Parenthesization/Grouping**: Any problem about optimal ways to group or parenthesize a sequence (expressions, matrices, strings).","**Game Theory on Sequences**: Two-player games where players take from ends or make choices over contiguous ranges.","**Merging/Splitting**: Problems involving costs of merging adjacent elements (e.g., merging stones, file concatenation).","**Palindrome Construction**: Building palindromes by considering what characters bracket the interval.","**Tree Construction from Sequences**: Building optimal trees where subtrees correspond to subintervals."],"title":{"icon":"Target","text":"Recognizing Interval DP Problems","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"rows":[["Matrix Chain Multiplication","Min cost for matrices i to j","Last multiplication position","O(n³)"],["Burst Balloons","Max coins in open interval (i,j)","Last balloon to burst","O(n³)"],["Optimal BST","Min expected cost for keys i to j","Root of subtree","O(n³)*"],["Minimum Score Triangulation","Min score for polygon vertices i to j","Third vertex of triangle with edge i-j","O(n³)"],["Palindrome Partitioning II","Min cuts for substring i to j","Position of last cut","O(n²)"],["Stone Game / Merge Stones","Min/max cost merging stones i to j","Where to split for final merge","O(n³)"],["Boolean Parenthesization","Ways to parenthesize for true/false","Position of outermost operator","O(n³)"]],"caption":"Classic Interval DP Problems","headers":["Problem","State Meaning","Split Interpretation","Time"]},"type":"table"},{"data":{"icon":"Zap","title":"The Three-Loop Structure","content":"Almost all interval DP solutions in tabulation form have the same three-loop structure:\n\n1. **Outer loop**: Iterate over interval lengths (from 1 or 2 up to n)\n2. **Middle loop**: Iterate over starting positions i\n3. **Inner loop**: Iterate over split points k within [i, j]\n\nThis gives O(n³) time. Recognize this structure, and implementing interval DP becomes mechanical.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"implementation-considerations","title":"Implementation Considerations and Optimizations","content":[{"data":{"content":"**Tabulation vs Memoization:**\n\nInterval DP can be implemented both ways:\n\n**Tabulation (Bottom-Up):**\n- Process intervals by increasing length\n- Explicit control over fill order\n- Slightly more cache-friendly\n- Easier to optimize space when possible\n\n**Memoization (Top-Down):**\n- More intuitive for complex recurrences\n- Naturally handles sparse subproblem usage\n- Easier to add pruning conditions\n- Stack depth can be O(n), potentially causing overflow for large n"},"type":"text"},{"data":{"left":[{"data":{"items":["**Off-by-one errors**: Be crystal clear whether intervals are [i,j] or (i,j).","**Forgetting base cases**: dp[i][i] and/or dp[i][i-1] need proper initialization.","**Wrong loop bounds**: Ensure j = i + length - 1 doesn't exceed array bounds.","**Incorrect split range**: k should typically go from i to j-1, not i to j."],"title":{"icon":"CheckCircle","text":"Common Pitfalls","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["**Knuth's Optimization**: For monotonic cost functions, reduces O(n³) to O(n²).","**Precompute costs**: Use prefix sums for range sum queries.","**Space reduction**: Sometimes only adjacent lengths needed.","**Early termination**: In memoization, add pruning when possible."],"title":{"icon":"Zap","text":"Optimization Techniques","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"Sparkles","title":"Knuth's Optimization","content":"For problems satisfying the **quadrangle inequality** (optimal split points are monotonic), Knuth's optimization constrains the search for optimal k. If opt[i][j] is the optimal split point:\n\nopt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]\n\nThis reduces the total inner loop iterations from O(n³) to O(n²). The Optimal BST problem can leverage this optimization.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"interval-dp-summary","title":"Summary: Mastering Interval DP","content":[{"data":{"content":"Interval DP is a powerful pattern that elegantly handles problems involving contiguous subintervals. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**State represents intervals**: `dp[i][j]` captures the optimal solution for the contiguous subinterval from index `i` to index `j`.","**Split point enumeration**: The recurrence tries all ways to divide the interval into two smaller intervals, combining their solutions.","**Process by length**: In tabulation, we fill the DP table in order of increasing interval length, ensuring dependencies are resolved.","**O(n³) is typical**: Most interval DP solutions require O(n³) time due to the three nested loops (length, start, split).","**Think backwards when helpful**: Problems like Burst Balloons become tractable by asking 'What is the LAST operation?' instead of 'What is the FIRST?'","**Applications are diverse**: Matrix chain, optimal trees, game theory, polygon triangulation, and many string problems all use this pattern."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand Interval DP—one of the most elegant and widely applicable DP patterns. The next page explores Bitmask DP, where we use binary representations to track which elements have been selected or processed, enabling efficient solutions for problems with small element counts but complex selection constraints.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7}],"isLocked":false},{"id":"seed_e856d7a691d49a4e55ad3f8a86e01111","title":"Bitmask DP (Conceptual)","order":1,"content":null,"isLocked":true},{"id":"seed_11af8d080eb81bb4d43e9dc7756e7ec8","title":"DP on Trees (Conceptual)","order":2,"content":null,"isLocked":true},{"id":"seed_485d13bdd13fd74b5958d33003621f1f","title":"DP with Multiple Constraints","order":3,"content":null,"isLocked":true}]}}