Pattern 4: Interval DP Problems

The Range Merging Pattern: State is dp[i][j] = answer for range/substring [i...j]. Build from small intervals to large. Try all split points k between i and j.

The Core Pattern

THE MENTAL MODEL

Imagine you have a rope with numbered segments:

You can only combine adjacent segments
Combining has a cost or value
You want to find the optimal way to combine all segments
You start with small ranges (2-3 segments) and build up to the full rope
For each range, you try all possible ways to split it

This is Interval DP.

Pattern Recognition

WHEN YOU SEE THIS PATTERN

Keywords: "substring", "subarray", "range [i...j]", "merge", "split", "palindrome", "optimal parenthesization"

Structure:

Operating on a contiguous range [i...j]
Answer for larger range depends on smaller sub-ranges
Need to try all ways to split the range

State: dp[i][j] = "best answer for range/substring from i to j"

Transition: Try all split points k between i and j:

dp[i][j] = best over all k of (dp[i][k] ⊕ dp[k+1][j] + merge_cost)

Build Order: By increasing length (length 1, 2, 3, ..., n)

Category 1: Core Interval DP Problems

1. Longest Palindromic Substring (LC 5)

PROBLEM

Given a string s, return the longest palindromic substring in s.

Example: s = "babad" → "bab" or "aba"

State Definition: dp[i][j] = true if substring s[i...j] is a palindrome

Transition:

dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i+1][j-1])

public String longestPalindrome(String s) {
    int n = s.length();
    if (n < 2) return s;

    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLen = 1;

    // Every single character is a palindrome
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    // Build by increasing length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;

            if (s.charAt(i) == s.charAt(j)) {
                // If length is 2 or inner substring is palindrome
                if (len == 2 || dp[i+1][j-1]) {
                    dp[i][j] = true;
                    start = i;
                    maxLen = len;
                }
            }
        }
    }

    return s.substring(start, start + maxLen);
}

THE FOUNDATION INSIGHT

Palindrome property: A string is a palindrome if:

First and last characters match
Inner substring is also a palindrome

This creates the interval dependency: dp[i][j] depends on dp[i+1][j-1]

2. Palindromic Substrings (LC 647)

State Definition: dp[i][j] = true if s[i...j] is palindrome

Goal: Count all palindromic substrings

Transition: Same as Longest Palindromic Substring, but count instead of tracking max

public int countSubstrings(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int count = 0;

    // Single characters
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
        count++;
    }

    // Build by length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;

            if (s.charAt(i) == s.charAt(j)) {
                if (len == 2 || dp[i+1][j-1]) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }
    }

    return count;
}

OPTIMIZATION VS COUNTING

Longest Palindromic Substring: Find the maximum length
Palindromic Substrings: Count all palindromes

Same structure, different goal!

3. Longest Palindromic Subsequence (LC 516)

PROBLEM

Given a string s, find the longest palindromic subsequence's length.

A subsequence is a sequence that can be derived from another by deleting some or no elements without changing the order.

Example: s = "bbbab" → 4 (subsequence "bbbb")

State Definition: dp[i][j] = length of longest palindromic subsequence in s[i...j]

Transition:

if (s[i] == s[j]) {
    dp[i][j] = 2 + dp[i+1][j-1];  // include both
} else {
    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);  // skip one
}

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];

    // Base case: single character
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // Build by increasing length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;

            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = 2 + (len == 2 ? 0 : dp[i+1][j-1]);
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }

    return dp[0][n-1];
}

SUBSTRING VS SUBSEQUENCE

Substring: Contiguous characters (must be adjacent)

dp[i][j] = is s[i...j] a palindrome? (boolean)

Subsequence: Non-contiguous (can skip characters)

dp[i][j] = longest palindrome length in s[i...j] (integer)

Key difference: Subsequence allows skipping characters!

4. Minimum Insertion Steps to Make String Palindrome (LC 1312)

State Definition: dp[i][j] = minimum insertions needed to make s[i...j] a palindrome

Transition:

if (s[i] == s[j]) {
    dp[i][j] = dp[i+1][j-1];  // no insertion needed
} else {
    dp[i][j] = 1 + Math.min(dp[i+1][j], dp[i][j-1]);  // insert one char
}

public int minInsertions(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;

            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = (len == 2) ? 0 : dp[i+1][j-1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i+1][j], dp[i][j-1]);
            }
        }
    }

    return dp[0][n-1];
}

RELATIONSHIP TO LONGEST PALINDROMIC SUBSEQUENCE

min_insertions = n - longest_palindromic_subsequence_length

Why? The characters NOT in the longest palindromic subsequence need to be inserted!

5. Burst Balloons (LC 312)

PROBLEM

You have n balloons. Each balloon has a number on it. You are asked to burst all balloons.

If you burst balloon i, you get nums[i-1] * nums[i] * nums[i+1] coins.

Return the maximum coins you can collect.

State Definition: dp[i][j] = max coins from bursting balloons in range [i...j]

Transition: Try bursting each balloon k LAST in range [i...j]:

dp[i][j] = max over all k in [i,j] of:
    dp[i][k-1] + dp[k+1][j] + nums[i-1] * nums[k] * nums[j+1]

public int maxCoins(int[] nums) {
    int n = nums.length;
    // Pad with 1s at both ends
    int[] arr = new int[n + 2];
    arr[0] = 1;
    arr[n + 1] = 1;
    for (int i = 0; i < n; i++) {
        arr[i + 1] = nums[i];
    }

    int[][] dp = new int[n + 2][n + 2];

    // Build by increasing length
    for (int len = 1; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;

            // Try bursting each balloon k LAST in [i, j]
            for (int k = i; k <= j; k++) {
                int coins = arr[i-1] * arr[k] * arr[j+1];
                coins += dp[i][k-1] + dp[k+1][j];
                dp[i][j] = Math.max(dp[i][j], coins);
            }
        }
    }

    return dp[1][n];
}

WHY "BURST LAST"?

The paradigm shift: Instead of thinking "which to burst first", think "which to burst LAST".

When balloon k bursts last in [i, j]:

All other balloons in [i, j] are already gone
Its neighbors are arr[i-1] and arr[j+1] (the boundaries!)
This makes subproblems independent

See the Burst Balloons: Paradigm Shift document for full explanation!

Category 2: Matrix/Partition Problems

6. Matrix Chain Multiplication (Classic)

PROBLEM

Given dimensions of n matrices in an array where the ith matrix has dimensions p[i-1] × p[i], find the minimum number of scalar multiplications needed to multiply all matrices.

Example: Matrices A1 (10×20), A2 (20×30), A3 (30×40)

(A1 × A2) × A3 = 10×20×30 + 10×30×40 = 18,000
A1 × (A2 × A3) = 20×30×40 + 10×20×40 = 32,000

State Definition: dp[i][j] = minimum operations to multiply matrices from i to j

Transition: Try all split points k:

dp[i][j] = min over all k in [i, j-1] of:
    dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]

public int matrixChainMultiplication(int[] p) {
    int n = p.length - 1;  // number of matrices
    int[][] dp = new int[n][n];

    // Base case: single matrix needs 0 operations
    // (already initialized to 0)

    // Build by increasing chain length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;

            // Try all split points
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n-1];
}

THE CLASSIC INTERVAL DP

This is THE textbook example of interval DP:

Range [i, j] = matrices from i to j
Split at k = decide where to place parentheses
Cost = operations for left + right + merging

Template for all partition problems!

7. Minimum Score Triangulation of Polygon (LC 1039)

State Definition: dp[i][j] = minimum score to triangulate polygon vertices from i to j

Transition: Try all vertices k as the third vertex of triangle:

dp[i][j] = min over all k in [i+1, j-1] of:
    dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]

public int minScoreTriangulation(int[] values) {
    int n = values.length;
    int[][] dp = new int[n][n];

    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;

            // Try all vertices k as third point of triangle
            for (int k = i + 1; k < j; k++) {
                int score = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
                dp[i][j] = Math.min(dp[i][j], score);
            }
        }
    }

    return dp[0][n-1];
}

GEOMETRIC INTERPRETATION

Each triangulation divides the polygon into smaller polygons.

Edge [i, j] + vertex k forms a triangle
Recursively triangulate [i, k] and [k, j]

Same structure as Matrix Chain Multiplication!

8. Minimum Cost Tree From Leaf Values (LC 1130)

State Definition: dp[i][j] = minimum sum of non-leaf nodes for subarray [i...j]

Transition: Split at k:

dp[i][j] = min over all k in [i, j-1] of:
    dp[i][k] + dp[k+1][j] + max[i..k] * max[k+1..j]

9. Minimum Cost to Merge Stones (LC 1000)

State Definition: dp[i][j][p] = minimum cost to merge stones [i...j] into p piles

Transition: 3D interval DP with pile count

3D INTERVAL DP

This extends interval DP with an extra dimension: number of piles remaining.

State: dp[i][j][piles]

10. Scramble String (LC 87)

State Definition: dp[i][j][len] = true if s1[i..i+len] can scramble to s2[j..j+len]

Transition: Try all split points, and try both swap and no-swap

public boolean isScramble(String s1, String s2) {
    if (s1.equals(s2)) return true;
    if (s1.length() != s2.length()) return false;

    int n = s1.length();
    boolean[][][] dp = new boolean[n][n][n + 1];

    // Base case: length 1
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
        }
    }

    // Build by increasing length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            for (int j = 0; j <= n - len; j++) {
                // Try all split points
                for (int k = 1; k < len; k++) {
                    // No swap: s1[i..i+k] → s2[j..j+k], s1[i+k..i+len] → s2[j+k..j+len]
                    if (dp[i][j][k] && dp[i+k][j+k][len-k]) {
                        dp[i][j][len] = true;
                        break;
                    }

                    // Swap: s1[i..i+k] → s2[j+len-k..j+len], s1[i+k..i+len] → s2[j..j+len-k]
                    if (dp[i][j+len-k][k] && dp[i+k][j][len-k]) {
                        dp[i][j][len] = true;
                        break;
                    }
                }
            }
        }
    }

    return dp[0][0][n];
}

Category 3: String Merging

11. Remove Boxes (LC 546)

State Definition: dp[i][j][k] = max points removing boxes [i...j] with k same-colored boxes adjacent after j

Transition: Try merging same-colored boxes at different positions

ADVANCED INTERVAL DP

This is one of the hardest interval DP problems.

3D State: [start][end][consecutive count]

Requires thinking about future merges with same colors.

12. Strange Printer (LC 664)

State Definition: dp[i][j] = minimum turns to print substring s[i...j]

Transition: Try last printed position k:

dp[i][j] = min over all k in [i, j-1] where s[k] == s[j] of:
    dp[i][k] + dp[k+1][j-1]

public int strangePrinter(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];

    // Base case: single character
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // Build by increasing length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = len;  // worst case: print each separately

            // Try to find matching character to merge prints
            for (int k = i; k < j; k++) {
                int total = dp[i][k] + dp[k+1][j];
                if (s.charAt(k) == s.charAt(j)) {
                    total--;  // can merge the prints
                }
                dp[i][j] = Math.min(dp[i][j], total);
            }
        }
    }

    return dp[0][n-1];
}

MERGING STRATEGY

When s[k] == s[j], we can print them together in one operation.

This is about finding optimal groupings of same characters.

13. Minimum Cost to Cut a Stick (LC 1547)

State Definition: dp[i][j] = minimum cost to make all cuts between positions i and j

Transition: Try cutting at each position k first:

dp[i][j] = min over all k in cuts between i and j of:
    dp[i][k] + dp[k][j] + (stick[j] - stick[i])

public int minCost(int n, int[] cuts) {
    int m = cuts.length;
    int[] newCuts = new int[m + 2];
    newCuts[0] = 0;
    newCuts[m + 1] = n;
    for (int i = 0; i < m; i++) {
        newCuts[i + 1] = cuts[i];
    }
    Arrays.sort(newCuts);

    int[][] dp = new int[m + 2][m + 2];

    // Build by increasing gap
    for (int len = 2; len < m + 2; len++) {
        for (int i = 0; i + len < m + 2; i++) {
            int j = i + len;
            dp[i][j] = Integer.MAX_VALUE;

            // Try all cuts between i and j
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = Math.min(
                    dp[i][j],
                    dp[i][k] + dp[k][j] + newCuts[j] - newCuts[i]
                );
            }
        }
    }

    return dp[0][m + 1];
}

14. Guess Number Higher or Lower II (LC 375)

State Definition: dp[i][j] = minimum cost to guarantee a win in range [i...j]

Transition: Try guessing each number k:

dp[i][j] = min over all k in [i, j] of:
    k + max(dp[i][k-1], dp[k+1][j])

public int getMoneyAmount(int n) {
    int[][] dp = new int[n + 1][n + 1];

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;

            for (int k = i; k <= j; k++) {
                int left = (k > i) ? dp[i][k-1] : 0;
                int right = (k < j) ? dp[k+1][j] : 0;
                dp[i][j] = Math.min(dp[i][j], k + Math.max(left, right));
            }
        }
    }

    return dp[1][n];
}

WORST-CASE OPTIMIZATION

We use max because we're preparing for the worst case (adversarial).

Then we minimize over all choices to find the best worst-case strategy.

15. Predict the Winner (LC 486)

State Definition: dp[i][j] = maximum score difference (player1 - player2) in range [i...j]

Transition: Player can take from either end:

dp[i][j] = max(
    nums[i] - dp[i+1][j],    // take left
    nums[j] - dp[i][j-1]     // take right
)

public boolean PredictTheWinner(int[] nums) {
    int n = nums.length;
    int[][] dp = new int[n][n];

    // Base case: single element
    for (int i = 0; i < n; i++) {
        dp[i][i] = nums[i];
    }

    // Build by increasing length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = Math.max(
                nums[i] - dp[i+1][j],   // take left
                nums[j] - dp[i][j-1]    // take right
            );
        }
    }

    return dp[0][n-1] >= 0;
}

GAME THEORY DP

State = score difference when playing optimally

Transition = max of (take item - opponent's best from remaining)

Negative sign because opponent's gain is your loss!

Category 4: Subsequence/Merging

16. Stone Game VII (LC 1690)

State Definition: dp[i][j] = maximum score difference in range [i...j]

Transition: Remove left or right stone, add sum of remaining:

dp[i][j] = max(
    sum[i+1..j] - dp[i+1][j],
    sum[i..j-1] - dp[i][j-1]
)

17. Palindrome Removal (LC 1246)

State Definition: dp[i][j] = minimum moves to remove all elements in [i...j]

Transition: Merge same elements, or split at k

18. Minimum Number of Removals to Make Mountain Array (LC 1671)

Approach: Find longest increasing subsequence from left and right

Interval-like: Build from both ends, find peak

19. Valid Parenthesis String (LC 678)

State Definition: dp[i][j] = true if s[i...j] is valid with wildcards

Transition: Try matching pairs at different positions

20. Number of Ways to Divide a Long Corridor (LC 2147)

State Definition: dp[i][j] = ways to partition [i...j] with seat constraints

Transition: Try placing dividers at valid positions

The Common Thread

WHAT MAKES THESE ALL THE SAME PATTERN?

Every problem has:

State: dp[i][j] = answer for subarray/substring from index i to j
Build order: Solve by increasing interval length (len = 1, 2, 3, ..., n)
Transition: Try all split points k where i ≤ k < j

Recurrence pattern:

dp[i][j] = best over all k of (dp[i][k] ⊕ dp[k+1][j] + merge_cost)

Goal: Combine solutions of smaller intervals to solve larger intervals

Key Insight: You can't solve dp[i][j] until you've solved all smaller intervals it depends on. This creates a dependency structure that requires careful iteration order.

Classic Loop Structures

Option 1: Build by Increasing Length

// Build by increasing length
for (int len = 2; len <= n; len++) {
    for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;

        // Try all split points
        for (int k = i; k < j; k++) {
            dp[i][j] = best(
                dp[i][j],
                dp[i][k] + dp[k+1][j] + merge_cost(i, k, j)
            );
        }
    }
}

Option 2: Iterate Backwards on i, Forwards on j

for (int i = n-1; i >= 0; i--) {
    for (int j = i; j < n; j++) {
        // transitions using dp[i+1][...] and dp[...][j-1]
        if (s[i] == s[j]) {
            dp[i][j] = 2 + dp[i+1][j-1];
        } else {
            dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
        }
    }
}

WHICH LOOP ORDER?

Length-based (Option 1):

More intuitive
Guarantees all dependencies computed
Works for all interval DP

Backwards-forwards (Option 2):

More compact
Works when dp[i][j] only depends on dp[i+1][...] and dp[...][j-1]
Common in palindrome problems

Both are correct if dependencies are respected!

Pattern Recognition Checklist

USE THIS CHECKLIST

When you see a new problem, ask:

Does it involve a range/substring [i...j]?
Does the answer for a range depend on smaller sub-ranges?
Do I need to try all ways to split or merge the range?
Can I define dp[i][j] as "best answer for range i to j"?
Do smaller ranges need to be solved before larger ones?

If all YES → Pattern 4: Interval DP

Common Mistakes

COMMON PITFALLS

Mistake 1: Wrong iteration order

// WRONG - may use uncomputed values
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        dp[i][j] = dp[i+1][j-1];  // i+1 not computed yet!
    }
}

// RIGHT - ensure dependencies computed first
for (int len = 1; len <= n; len++) {
    for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;
        // now dp[i+1][j-1] is already computed
    }
}

Mistake 2: Boundary conditions

// WRONG - accessing out of bounds
dp[i][j] = dp[i-1][j-1];  // what if i=0 or j=0?

// RIGHT - check boundaries
if (i > 0 && j > 0) {
    dp[i][j] = dp[i-1][j-1];
}

Mistake 3: Base case initialization

// Palindrome: single characters
for (int i = 0; i < n; i++) {
    dp[i][i] = true;  // or 1, depending on problem
}

// Matrix chain: single matrix
// dp[i][i] = 0 (no multiplication needed)

Space Optimization

INTERVAL DP IS HARD TO OPTIMIZE

Unlike linear or grid DP, interval DP is difficult to space-optimize because:

dp[i][j] depends on dp[i][k] and dp[k+1][j] for various k
You need to access many positions in the 2D table
Rolling array technique doesn't work well

Usually keep O(n²) space for interval DP.

Exception: Some palindrome problems can be optimized to O(n) with expand-from-center approach instead of DP.

Learning Path

RECOMMENDED ORDER

Week 1: Palindromes (Problems 1-4)

Master palindrome interval DP
Learn length-based iteration
Understand substring vs subsequence

Week 2: Partitioning (Problems 5-10)

Matrix Chain Multiplication template
Burst Balloons paradigm shift
Triangulation and merging

Week 3: String Merging (Problems 11-15)

Advanced 3D interval DP
Game theory applications
Worst-case optimization

Week 4: Advanced (Problems 16-20)

Stone games
Complex constraints
Multi-dimensional intervals

Total: 20 problems × 4 weeks = Pattern 4 mastery

Quick Reference Table

Problem	State	Split/Merge	Operation	Pattern Type
Longest Palindrome	is [i,j] palindrome	match ends	check chars	Boolean
Palindrome Subseq	max length in [i,j]	match/skip	max	Optimization
Burst Balloons	max coins in [i,j]	burst k last	max + cost	Partition
Matrix Chain	min ops for [i,j]	split at k	min + cost	Classic
Strange Printer	min turns for [i,j]	merge same	min	Merging
Predict Winner	score diff in [i,j]	take left/right	max(gain - opp)	Game Theory
Min Cost Cut	min cost cuts [i,j]	cut at k	min + length	Partition

Dependency Visualization

UNDERSTANDING DEPENDENCIES

For dp[i][j], typical dependencies:

Palindrome pattern:

dp[i][j] depends on:
  - dp[i+1][j-1]  (inner substring)

Partition pattern:

dp[i][j] depends on:
  - dp[i][k] and dp[k+1][j]  for all k in [i, j]

Visualization (for 4x4 table):

 1   2   3
[X] [1] [2] [3]
    [X] [1] [2]
        [X] [1]
            [X]

X = base case
= computed in round 1 (length 2)
= computed in round 2 (length 3)
= computed in round 3 (length 4)

Diagonal filling: bottom-left to top-right, by diagonal

Next Steps

AFTER MASTERING PATTERN 4

You're ready for:

Pattern 5: State Machine DP (mode transitions)
Advanced DP: Multi-dimensional intervals
DP on Trees (hierarchical intervals)

Connection to Previous Patterns:

Pattern 1: 1D state (single position)
Pattern 2: 2D state (two independent positions)
Pattern 3: 2D state (items + resource)
Pattern 4: 2D state (range endpoints) ← Dependent positions!

Final Thoughts

INTERVAL DP IS THE MERGING PATTERN

Interval DP teaches you to think about ranges and merging.

Master these 20 problems, and you'll:

Recognize "try all split points" instantly
Know when to use length-based iteration
Handle palindromes, partitions, games naturally
Understand dependency structures in 2D DP

This is your range-based foundation. Build it strong.

Summary: The Interval DP Template

// Template for Interval DP
public int intervalDP(int[] arr) {
    int n = arr.length;
    int[][] dp = new int[n][n];

    // Base case: intervals of length 1
    for (int i = 0; i < n; i++) {
        dp[i][i] = baseValue(i);
    }

    // Build by increasing length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = initValue;  // MAX_VALUE for min, MIN_VALUE for max

            // Try all split points
            for (int k = i; k < j; k++) {
                dp[i][j] = best(
                    dp[i][j],
                    combine(dp[i][k], dp[k+1][j], mergeCost(i, k, j))
                );
            }
        }
    }

    return dp[0][n-1];
}

REMEMBER THE MANTRA

"For each range [i,j], try all ways to split it at k. The answer is the best combination of [i,k] and [k+1,j] plus the cost of merging."

This is the essence of Interval DP.

The Core Pattern​

Pattern Recognition​

Category 1: Core Interval DP Problems​

1. Longest Palindromic Substring (LC 5)​

2. Palindromic Substrings (LC 647)​

3. Longest Palindromic Subsequence (LC 516)​

4. Minimum Insertion Steps to Make String Palindrome (LC 1312)​

5. Burst Balloons (LC 312)​

Category 2: Matrix/Partition Problems​

6. Matrix Chain Multiplication (Classic)​

7. Minimum Score Triangulation of Polygon (LC 1039)​

8. Minimum Cost Tree From Leaf Values (LC 1130)​

9. Minimum Cost to Merge Stones (LC 1000)​

10. Scramble String (LC 87)​

Category 3: String Merging​

11. Remove Boxes (LC 546)​

12. Strange Printer (LC 664)​

13. Minimum Cost to Cut a Stick (LC 1547)​

14. Guess Number Higher or Lower II (LC 375)​

15. Predict the Winner (LC 486)​

Category 4: Subsequence/Merging​

16. Stone Game VII (LC 1690)​

17. Palindrome Removal (LC 1246)​

18. Minimum Number of Removals to Make Mountain Array (LC 1671)​

19. Valid Parenthesis String (LC 678)​

20. Number of Ways to Divide a Long Corridor (LC 2147)​

The Common Thread​

Classic Loop Structures​

Option 1: Build by Increasing Length​

Option 2: Iterate Backwards on i, Forwards on j​

Pattern Recognition Checklist​

Common Mistakes​

Mistake 1: Wrong iteration order​

Mistake 2: Boundary conditions​

Mistake 3: Base case initialization​

Space Optimization​

Learning Path​

Quick Reference Table​

Dependency Visualization​

Next Steps​

Final Thoughts​

Summary: The Interval DP Template​

The Core Pattern

Pattern Recognition

Category 1: Core Interval DP Problems

1. Longest Palindromic Substring (LC 5)

2. Palindromic Substrings (LC 647)

3. Longest Palindromic Subsequence (LC 516)

4. Minimum Insertion Steps to Make String Palindrome (LC 1312)

5. Burst Balloons (LC 312)

Category 2: Matrix/Partition Problems

6. Matrix Chain Multiplication (Classic)

7. Minimum Score Triangulation of Polygon (LC 1039)

8. Minimum Cost Tree From Leaf Values (LC 1130)

9. Minimum Cost to Merge Stones (LC 1000)

10. Scramble String (LC 87)

Category 3: String Merging

11. Remove Boxes (LC 546)

12. Strange Printer (LC 664)

13. Minimum Cost to Cut a Stick (LC 1547)

14. Guess Number Higher or Lower II (LC 375)

15. Predict the Winner (LC 486)

Category 4: Subsequence/Merging

16. Stone Game VII (LC 1690)

17. Palindrome Removal (LC 1246)

18. Minimum Number of Removals to Make Mountain Array (LC 1671)

19. Valid Parenthesis String (LC 678)

20. Number of Ways to Divide a Long Corridor (LC 2147)

The Common Thread

Classic Loop Structures

Option 1: Build by Increasing Length

Option 2: Iterate Backwards on i, Forwards on j

Pattern Recognition Checklist

Common Mistakes

Mistake 1: Wrong iteration order

Mistake 2: Boundary conditions

Mistake 3: Base case initialization

Space Optimization

Learning Path

Quick Reference Table

Dependency Visualization

Next Steps

Final Thoughts

Summary: The Interval DP Template