Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Matrix Chain Multiplication
DSA

Matrix Chain Multiplication

Understand the classic interval DP problem of finding the minimum cost of multiplying a sequence of matrices.

The Matrix Chain Multiplication (MCM) pattern is one of the most important applications of Interval DP and Partition DP.

At its core, MCM asks:

“Where should I split the problem to obtain the optimal answer?”

The pattern extends beyond matrix multiplication to problems involving:

  • intervals
  • partition points
  • parenthesization
  • cutting
  • merging
  • removing elements
  • choosing a last operation
  • combining left and right subproblems

Focus on recognizing:

“Range + split at k + left/right subproblems + optimize/count” = MCM / Partition DP

Pattern Table

PatternTypical Question TypesKeywordsCore Idea
Matrix Chain MultiplicationMinimum multiplication costmultiply, parenthesizeTry every split
Palindrome PartitioningMinimum cutspalindrome, partition, cutsTry every cut
Minimum Cost to Cut a StickMinimum cutting costcut, segment, costChoose first/last cut
Burst BalloonsMaximum coinsburst, remove, maximizeChoose last balloon
Boolean ParenthesizationCount evaluationstrue, false, operatorsSplit at operators
Optimal BSTMinimum search costBST, root, frequencyChoose root
Merge StonesMinimum merge costmerge, adjacent, pilesTry partition points
Scramble StringString transformationscramble, splitTry every split
Expression EvaluationCount possible resultsexpression, operatorsSplit expression
Polygon TriangulationMinimum triangulation scorepolygon, triangleChoose third vertex

Mini Notes / Tips

### Tips

- MCM usually uses an interval state such as dp[i][j].
- First define exactly what dp[i][j] represents.
- Most problems try every partition point k.
- Build smaller intervals before larger intervals.
- Ask whether the operation should be chosen first or last.
- "Choose last" is especially useful for removal problems.
- The answer may be:
  - minimum
  - maximum
  - count
  - boolean
- Some variations need extra dimensions such as:
  - dp[i][j][isTrue]
  - dp[i][j][len]
  - dp[i][j][extraState]

MCM Pattern – Detection & Usage Guide

1. Matrix Chain Multiplication – Very Common

Matrix Chain Multiplication

Find the parenthesization that minimizes scalar multiplications for a chain of matrices.

dp[i][j] = min over split k of dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j]. Fill by increasing interval length so smaller subchains are ready first. O(n³); the answer is dp[1][n] and the split point tells you where to cut.

GRID VISUALIZER
Steps –
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        for len in 2..n:
                      
                        2
                          for i in 1..n-len+1:
                      
                        3
                            j = i + len - 1
                      
                        4
                            dp[i][j] = min over k in i..j-1 of
                      
                        5
                              dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
                      
                        6
                        return dp[1][n]

When to use / Detection cues

  • Input: Matrix dimensions.
  • Keywords: multiply, parenthesize, minimum cost.
  • Hint: Different multiplication orders have different costs.
  • Core idea: Try every place to split the chain.

State

dp[i][j]
=
minimum cost to multiply matrices i through j

Transition

dp[i][j] =
min(
    dp[i][k]
    + dp[k+1][j]
    + dims[i-1] * dims[k] * dims[j]
)

where:

i <= k < j

Java Template

public int matrixChainMultiplication(int[] dims) {
    int n = dims.length - 1;

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

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

            dp[i][j] = Integer.MAX_VALUE;

            for (int k = i; k < j; k++) {
                int cost =
                    dp[i][k]
                    + dp[k + 1][j]
                    + dims[i - 1] * dims[k] * dims[j];

                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }

    return dp[1][n];
}
def matrix_chain_multiplication(dims):
    n = len(dims) - 1

    dp = [[0] * (n + 1) for _ in range(n + 1)]

    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]
                    + dims[i - 1] * dims[k] * dims[j]
                )

                dp[i][j] = min(dp[i][j], cost)

    return dp[1][n]
int matrixChainMultiplication(vector<int>& dims) {
    int n = dims.size() - 1;

    vector<vector<int>> dp(n + 1, vector<int>(n + 1));

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

            dp[i][j] = INT_MAX;

            for (int k = i; k < j; k++) {
                int cost =
                    dp[i][k]
                    + dp[k + 1][j]
                    + dims[i - 1] * dims[k] * dims[j];

                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }

    return dp[1][n];
}
function matrixChainMultiplication(dims) {
  const n = dims.length - 1;

  const dp = Array.from({ length: n + 1 }, () =>
    new Array(n + 1).fill(0)
  );

  for (let len = 2; len <= n; len++) {
    for (let i = 1; i + len - 1 <= n; 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] +
          dims[i - 1] * dims[k] * dims[j];

        dp[i][j] = Math.min(dp[i][j], cost);
      }
    }
  }

  return dp[1][n];
}

Complexity

Time:  O(n³)
Space: O(n²)

Mental trigger

Different parenthesizations → try every split → MCM.

2. Palindrome Partitioning – Very Common

Palindrome Partitioning

Cut a string into all combinations of palindromic pieces.

At each position try every prefix; keep it only if it is a palindrome, then recurse on the remainder. Non-palindrome prefixes die immediately, pruning the exponential tree. The valid partitions that reach the end are the answers.

TREE VISUALIZER
Steps –
"aab"take"a"→"ab"take"ab"✗take"a"→"b"take"b"✓take"aa"→"b"
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        partition(start, path):
                      
                        2
                          if start == len(s): output path
                      
                        3
                          for end in start+1 .. len(s):
                      
                        4
                            prefix = s[start:end]
                      
                        5
                            if isPalindrome(prefix):
                      
                        6
                              partition(end, path + [prefix])

When to use / Detection cues

  • Input: String.
  • Keywords: palindrome, partition, minimum cuts.
  • Hint: Split the string into valid palindrome pieces.
  • Core idea: Try every possible next partition.

There are two common approaches:

Approach 1:
Interval DP

Approach 2:
Partition DP + palindrome preprocessing

Java Template – Partition DP

public int minCut(String s) {
    int n = s.length();

    boolean[][] palindrome = new boolean[n][n];

    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s.charAt(i) == s.charAt(j) &&
                (j - i <= 2 || palindrome[i + 1][j - 1])) {
                palindrome[i][j] = true;
            }
        }
    }

    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);

    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (palindrome[j][i - 1]) {
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
    }

    return dp[n] - 1;
}
def min_cut(s):
    n = len(s)

    palindrome = [[False] * n for _ in range(n)]

    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (
                j - i <= 2 or palindrome[i + 1][j - 1]
            ):
                palindrome[i][j] = True

    dp = [float('inf')] * (n + 1)

    dp[0] = 0

    for i in range(1, n + 1):
        for j in range(i):
            if palindrome[j][i - 1]:
                dp[i] = min(dp[i], dp[j] + 1)

    return dp[n] - 1
int minCut(string s) {
    int n = s.size();

    vector<vector<bool>> palindrome(
        n, vector<bool>(n, false));

    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s[i] == s[j] &&
                (j - i <= 2 || palindrome[i + 1][j - 1])) {
                palindrome[i][j] = true;
            }
        }
    }

    vector<int> dp(n + 1, INT_MAX);

    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (palindrome[j][i - 1]) {
                dp[i] = min(dp[i], dp[j] + 1);
            }
        }
    }

    return dp[n] - 1;
}
function minCut(s) {
  const n = s.length;

  const palindrome = Array.from({ length: n }, () =>
    new Array(n).fill(false)
  );

  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      if (
        s[i] === s[j] &&
        (j - i <= 2 || palindrome[i + 1][j - 1])
      ) {
        palindrome[i][j] = true;
      }
    }
  }

  const dp = new Array(n + 1).fill(Infinity);

  dp[0] = 0;

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (palindrome[j][i - 1]) {
        dp[i] = Math.min(dp[i], dp[j] + 1);
      }
    }
  }

  return dp[n] - 1;
}

Mental trigger

“Where should I cut the string?” → Partition DP.

3. Minimum Cost to Cut a Stick – Common

Minimum Cost to Cut a Stick

Cut a stick at given positions with minimum total cost.

Cost to cut a segment = its length, plus cost of cutting the two resulting pieces. dp[i][j] = min over an internal cut k of (length + dp[i][k] + dp[k][j]). Solve short intervals first. O(n³) time.

GRID VISUALIZER
Steps –
0
0
2
5
8
0
0
0
2
5
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        add 0 and n to cuts -> pts
                      
                        2
                        for len in 2..m:
                      
                        3
                          for i in 0..m-len:
                      
                        4
                            j = i + len
                      
                        5
                            dp[i][j] = min_k( pts[j]-pts[i] + dp[i][k] + dp[k][j] )
                      
                        6
                        return dp[0][m]

When to use / Detection cues

  • Input: Stick length + cut positions.
  • Keywords: cut, minimum cost.
  • Hint: Every cut divides the current segment.
  • Core idea: Choose which cut happens first inside the interval.

Add boundaries:

0
cuts...
length

State

dp[i][j]
=
minimum cost to perform all cuts between cuts[i] and cuts[j]

Java Template

public int minCost(int n, int[] cuts) {
    int m = cuts.length;

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

    for (int i = 0; i < m; i++) {
        points[i + 1] = cuts[i];
    }

    points[0] = 0;
    points[m + 1] = n;

    Arrays.sort(points);

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

    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;

            for (int k = i + 1; k < j; k++) {
                int cost =
                    dp[i][k]
                    + dp[k][j]
                    + points[j] - points[i];

                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }

    return dp[0][m + 1];
}
def min_cost(n, cuts):
    m = len(cuts)

    points = [0] * (m + 2)

    for i in range(m):
        points[i + 1] = cuts[i]

    points[0] = 0
    points[m + 1] = n

    points.sort()

    dp = [[0] * (m + 2) for _ in range(m + 2)]

    for length in range(2, m + 2):
        for i in range(m + 2 - length):
            j = i + length

            dp[i][j] = float('inf')

            for k in range(i + 1, j):
                cost = (
                    dp[i][k]
                    + dp[k][j]
                    + points[j] - points[i]
                )

                dp[i][j] = min(dp[i][j], cost)

    return dp[0][m + 1]
int minCost(int n, vector<int>& cuts) {
    int m = cuts.size();

    vector<int> points(m + 2);

    for (int i = 0; i < m; i++) {
        points[i + 1] = cuts[i];
    }

    points[0] = 0;
    points[m + 1] = n;

    sort(points.begin(), points.end());

    vector<vector<int>> dp(m + 2, vector<int>(m + 2));

    for (int len = 2; len < m + 2; len++) {
        for (int i = 0; i + len < m + 2; i++) {
            int j = i + len;

            dp[i][j] = INT_MAX;

            for (int k = i + 1; k < j; k++) {
                int cost =
                    dp[i][k]
                    + dp[k][j]
                    + points[j] - points[i];

                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }

    return dp[0][m + 1];
}
function minCost(n, cuts) {
  const m = cuts.length;

  const points = new Array(m + 2);

  for (let i = 0; i < m; i++) {
    points[i + 1] = cuts[i];
  }

  points[0] = 0;
  points[m + 1] = n;

  points.sort((a, b) => a - b);

  const dp = Array.from({ length: m + 2 }, () =>
    new Array(m + 2).fill(0)
  );

  for (let len = 2; len < m + 2; len++) {
    for (let i = 0; i + len < m + 2; i++) {
      const j = i + len;

      dp[i][j] = Infinity;

      for (let k = i + 1; k < j; k++) {
        const cost =
          dp[i][k] + dp[k][j] + points[j] - points[i];

        dp[i][j] = Math.min(dp[i][j], cost);
      }
    }
  }

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

Mental trigger

“A cut splits a segment” → Interval DP.

4. Burst Balloons – Very Common

Burst Balloons (Interval DP)

Compute the maximum coins from bursting balloons i..j using interval DP.

Build dp[i][j] bottom-up: for each interval pick the last balloon k to burst, scoring nums[i-1]*nums[k]*nums[j+1] plus the already-solved subintervals dp[i][k-1] and dp[k+1][j]. Padding the array with 1s at both ends handles the edges. O(n³) time, O(n²) space.

GRID VISUALIZER
Steps –
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        dp[i][j] = max score bursting balloons i..j
                      
                        2
                        for len in 1..n:
                      
                        3
                          for i in 1..n-len+1:
                      
                        4
                            j = i + len - 1
                      
                        5
                            dp[i][j] = max over k in i..j of
                      
                        6
                              dp[i][k-1] + dp[k+1][j] + nums[i-1]*nums[k]*nums[j+1]
                      
                        7
                        return dp[1][n]

When to use / Detection cues

  • Input: Array where elements are removed.
  • Keywords: burst, remove, maximize coins.
  • Hint: Bursting first makes neighboring values change.
  • Core idea: Instead of choosing the first balloon, choose the last balloon.

Add boundaries:

1  + original array +  1

State

dp[i][j]
=
maximum coins from bursting balloons i through j

Transition

dp[i][j] =
max(
    dp[i][k-1]
    + dp[k+1][j]
    + nums[i-1] * nums[k] * nums[j+1]
)

Java Template

public int maxCoins(int[] nums) {
    int n = nums.length;

    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];

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

            for (int k = i; k <= j; k++) {
                int coins =
                    dp[i][k - 1]
                    + dp[k + 1][j]
                    + arr[i - 1] * arr[k] * arr[j + 1];

                dp[i][j] = Math.max(dp[i][j], coins);
            }
        }
    }

    return dp[1][n];
}
def max_coins(nums):
    n = len(nums)

    arr = [0] * (n + 2)

    arr[0] = 1
    arr[n + 1] = 1

    for i in range(n):
        arr[i + 1] = nums[i]

    dp = [[0] * (n + 2) for _ in range(n + 2)]

    for length in range(1, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1

            for k in range(i, j + 1):
                coins = (
                    dp[i][k - 1]
                    + dp[k + 1][j]
                    + arr[i - 1] * arr[k] * arr[j + 1]
                )

                dp[i][j] = max(dp[i][j], coins)

    return dp[1][n]
int maxCoins(vector<int>& nums) {
    int n = nums.size();

    vector<int> arr(n + 2);

    arr[0] = 1;
    arr[n + 1] = 1;

    for (int i = 0; i < n; i++) {
        arr[i + 1] = nums[i];
    }

    vector<vector<int>> dp(n + 2, vector<int>(n + 2));

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

            for (int k = i; k <= j; k++) {
                int coins =
                    dp[i][k - 1]
                    + dp[k + 1][j]
                    + arr[i - 1] * arr[k] * arr[j + 1];

                dp[i][j] = max(dp[i][j], coins);
            }
        }
    }

    return dp[1][n];
}
function maxCoins(nums) {
  const n = nums.length;

  const arr = new Array(n + 2).fill(0);

  arr[0] = 1;
  arr[n + 1] = 1;

  for (let i = 0; i < n; i++) {
    arr[i + 1] = nums[i];
  }

  const dp = Array.from({ length: n + 2 }, () =>
    new Array(n + 2).fill(0)
  );

  for (let len = 1; len <= n; len++) {
    for (let i = 1; i + len - 1 <= n; i++) {
      const j = i + len - 1;

      for (let k = i; k <= j; k++) {
        const coins =
          dp[i][k - 1] +
          dp[k + 1][j] +
          arr[i - 1] * arr[k] * arr[j + 1];

        dp[i][j] = Math.max(dp[i][j], coins);
      }
    }
  }

  return dp[1][n];
}

Mental trigger

“Removal order changes neighbors” → Think backwards → Choose the last operation.

5. Boolean Parenthesization – Common

Boolean Parenthesization

Count ways to parenthesize a boolean expression to evaluate true.

For each substring, count ways to get true (T) and false (F). Combine left and right counts using the operator: &, |, ^. dp over all substrings, shortest first. O(n³) time.

GRID VISUALIZER
Steps –
0
1
2
3
1
5
4
10
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        T[i][i] = (s[i] == 'T'); F[i][i] = !T[i][i]
                      
                        2
                        for len in 2..n:
                      
                        3
                          for i in 0..n-len:
                      
                        4
                            j = i + len - 1
                      
                        5
                            for k in i..j-1: combine T/F by op(k)
                      
                        6
                        return T[0][n-1]

When to use / Detection cues

  • Input: Boolean expression.
  • Keywords: true, false, operators, parenthesization.
  • Hint: Different parenthesizations produce different results.
  • Core idea: Every operator can become a partition point.

State

dp[i][j][0] = ways expression i..j evaluates to false
dp[i][j][1] = ways expression i..j evaluates to true

Java Template

public long countWays(String exp) {
    int n = exp.length();

    long[][][] dp = new long[n][n][2];

    for (int i = 0; i < n; i += 2) {
        dp[i][i][1] = exp.charAt(i) == 'T' ? 1 : 0;
        dp[i][i][0] = exp.charAt(i) == 'F' ? 1 : 0;
    }

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

            for (int k = i + 1; k < j; k += 2) {
                char op = exp.charAt(k);

                long leftTrue = dp[i][k - 1][1];
                long leftFalse = dp[i][k - 1][0];

                long rightTrue = dp[k + 1][j][1];
                long rightFalse = dp[k + 1][j][0];

                if (op == '&') {
                    dp[i][j][1] += leftTrue * rightTrue;
                    dp[i][j][0] +=
                        leftFalse * rightTrue
                        + leftTrue * rightFalse
                        + leftFalse * rightFalse;

                } else if (op == '|') {
                    dp[i][j][1] +=
                        leftTrue * rightTrue
                        + leftTrue * rightFalse
                        + leftFalse * rightTrue;

                    dp[i][j][0] += leftFalse * rightFalse;

                } else if (op == '^') {
                    dp[i][j][1] +=
                        leftTrue * rightFalse
                        + leftFalse * rightTrue;

                    dp[i][j][0] +=
                        leftTrue * rightTrue
                        + leftFalse * rightFalse;
                }
            }
        }
    }

    return dp[0][n - 1][1];
}
def count_ways(exp):
    n = len(exp)

    # dp[i][j][0]: false ways, dp[i][j][1]: true ways
    dp = [[[0, 0] for _ in range(n)] for _ in range(n)]

    for i in range(0, n, 2):
        dp[i][i][1] = 1 if exp[i] == 'T' else 0
        dp[i][i][0] = 1 if exp[i] == 'F' else 0

    for length in range(3, n + 1, 2):
        for i in range(0, n - length + 1, 2):
            j = i + length - 1

            for k in range(i + 1, j, 2):
                op = exp[k]

                left_true = dp[i][k - 1][1]
                left_false = dp[i][k - 1][0]

                right_true = dp[k + 1][j][1]
                right_false = dp[k + 1][j][0]

                if op == '&':
                    dp[i][j][1] += left_true * right_true
                    dp[i][j][0] += (
                        left_false * right_true
                        + left_true * right_false
                        + left_false * right_false
                    )

                elif op == '|':
                    dp[i][j][1] += (
                        left_true * right_true
                        + left_true * right_false
                        + left_false * right_true
                    )

                    dp[i][j][0] += left_false * right_false

                elif op == '^':
                    dp[i][j][1] += (
                        left_true * right_false
                        + left_false * right_true
                    )

                    dp[i][j][0] += (
                        left_true * right_true
                        + left_false * right_false
                    )

    return dp[0][n - 1][1]
long long countWays(string exp) {
    int n = exp.size();

    vector<vector<array<long long, 2>>> dp(
        n,
        vector<array<long long, 2>>(
            n, array<long long, 2>{0, 0}));

    for (int i = 0; i < n; i += 2) {
        dp[i][i][1] = exp[i] == 'T' ? 1 : 0;
        dp[i][i][0] = exp[i] == 'F' ? 1 : 0;
    }

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

            for (int k = i + 1; k < j; k += 2) {
                char op = exp[k];

                long long leftTrue = dp[i][k - 1][1];
                long long leftFalse = dp[i][k - 1][0];

                long long rightTrue = dp[k + 1][j][1];
                long long rightFalse = dp[k + 1][j][0];

                if (op == '&') {
                    dp[i][j][1] += leftTrue * rightTrue;
                    dp[i][j][0] +=
                        leftFalse * rightTrue
                        + leftTrue * rightFalse
                        + leftFalse * rightFalse;

                } else if (op == '|') {
                    dp[i][j][1] +=
                        leftTrue * rightTrue
                        + leftTrue * rightFalse
                        + leftFalse * rightTrue;

                    dp[i][j][0] += leftFalse * rightFalse;

                } else if (op == '^') {
                    dp[i][j][1] +=
                        leftTrue * rightFalse
                        + leftFalse * rightTrue;

                    dp[i][j][0] +=
                        leftTrue * rightTrue
                        + leftFalse * rightFalse;
                }
            }
        }
    }

    return dp[0][n - 1][1];
}
function countWays(exp) {
  const n = exp.length;

  const dp = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => [0, 0])
  );

  for (let i = 0; i < n; i += 2) {
    dp[i][i][1] = exp[i] === 'T' ? 1 : 0;
    dp[i][i][0] = exp[i] === 'F' ? 1 : 0;
  }

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

      for (let k = i + 1; k < j; k += 2) {
        const op = exp[k];

        const leftTrue = dp[i][k - 1][1];
        const leftFalse = dp[i][k - 1][0];

        const rightTrue = dp[k + 1][j][1];
        const rightFalse = dp[k + 1][j][0];

        if (op === '&') {
          dp[i][j][1] += leftTrue * rightTrue;
          dp[i][j][0] +=
            leftFalse * rightTrue +
            leftTrue * rightFalse +
            leftFalse * rightFalse;
        } else if (op === '|') {
          dp[i][j][1] +=
            leftTrue * rightTrue +
            leftTrue * rightFalse +
            leftFalse * rightTrue;

          dp[i][j][0] += leftFalse * rightFalse;
        } else if (op === '^') {
          dp[i][j][1] +=
            leftTrue * rightFalse +
            leftFalse * rightTrue;

          dp[i][j][0] +=
            leftTrue * rightTrue + leftFalse * rightFalse;
        }
      }
    }
  }

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

Mental trigger

“Count ways to evaluate expression” → Split at every operator.

6. Optimal BST – Moderate

Optimal Binary Search Tree

Build a BST with minimum expected search cost.

dp[i][j] = min cost BST from keys i..j. Cost = sum of frequencies in the range + best root's (left cost + right cost). Try every key as root. O(n³) time.

GRID VISUALIZER
Steps –
0
1
6
12
0
0
2
10
0
0
0
3
0
0
0
0
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        freqSum(i,j) = sum of freqs i..j
                      
                        2
                        dp[i][i] = freq[i]
                      
                        3
                        for len in 2..n:
                      
                        4
                          for i in 0..n-len:
                      
                        5
                            j = i + len - 1
                      
                        6
                            dp[i][j] = min_k( freqSum(i,j) + dp[i][k-1] + dp[k+1][j] )
                      
                        7
                        return dp[0][n-1]

When to use / Detection cues

  • Input: Ordered keys with frequencies.
  • Keywords: BST, root, search cost.
  • Hint: Choosing a root divides the keys into left and right subtrees.
  • Core idea: Try every key as the root.

State

dp[i][j]
=
minimum search cost for keys i..j

Java Template

public int optimalBST(int[] keys, int[] freq) {
    int n = keys.length;

    int[] prefix = new int[n + 1];

    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + freq[i];
    }

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

    for (int i = 0; i < n; i++) {
        dp[i][i] = freq[i];
    }

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

            dp[i][j] = Integer.MAX_VALUE;

            int totalFreq =
                prefix[j + 1] - prefix[i];

            for (int root = i; root <= j; root++) {

                int left =
                    root > i ? dp[i][root - 1] : 0;

                int right =
                    root < j ? dp[root + 1][j] : 0;

                dp[i][j] =
                    Math.min(
                        dp[i][j],
                        left + right + totalFreq
                    );
            }
        }
    }

    return dp[0][n - 1];
}
def optimal_bst(keys, freq):
    n = len(keys)

    prefix = [0] * (n + 1)

    for i in range(n):
        prefix[i + 1] = prefix[i] + freq[i]

    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = freq[i]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            dp[i][j] = float('inf')

            total_freq = prefix[j + 1] - prefix[i]

            for root in range(i, j + 1):

                left = dp[i][root - 1] if root > i else 0

                right = dp[root + 1][j] if root < j else 0

                dp[i][j] = min(
                    dp[i][j],
                    left + right + total_freq
                )

    return dp[0][n - 1]
int optimalBST(vector<int>& keys, vector<int>& freq) {
    int n = keys.size();

    vector<int> prefix(n + 1);

    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + freq[i];
    }

    vector<vector<int>> dp(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        dp[i][i] = freq[i];
    }

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

            dp[i][j] = INT_MAX;

            int totalFreq =
                prefix[j + 1] - prefix[i];

            for (int root = i; root <= j; root++) {

                int left =
                    root > i ? dp[i][root - 1] : 0;

                int right =
                    root < j ? dp[root + 1][j] : 0;

                dp[i][j] =
                    min(
                        dp[i][j],
                        left + right + totalFreq
                    );
            }
        }
    }

    return dp[0][n - 1];
}
function optimalBST(keys, freq) {
  const n = keys.length;

  const prefix = new Array(n + 1).fill(0);

  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + freq[i];
  }

  const dp = Array.from({ length: n }, () =>
    new Array(n).fill(0)
  );

  for (let i = 0; i < n; i++) {
    dp[i][i] = freq[i];
  }

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

      dp[i][j] = Infinity;

      const totalFreq = prefix[j + 1] - prefix[i];

      for (let root = i; root <= j; root++) {
        const left = root > i ? dp[i][root - 1] : 0;

        const right = root < j ? dp[root + 1][j] : 0;

        dp[i][j] = Math.min(
          dp[i][j],
          left + right + totalFreq
        );
      }
    }
  }

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

Mental trigger

“Which element should become the root?” → Interval DP.

7. Merge Stones – Moderate

Merge Stones (Min Cost)

Merge adjacent piles until one remains, minimizing total cost.

dp[i][j] = min cost to merge piles i..j into one. Cost = sum of the range + best split into left/right merges. Use prefix sums for the range total. O(n³) time.

GRID VISUALIZER
Steps –
0
0
3
9
19
0
0
0
3
16
0
0
0
0
7
0
0
0
0
0
0
0
0
0
0
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        ps = prefix sums of piles
                      
                        2
                        for len in 2..n:
                      
                        3
                          for i in 0..n-len:
                      
                        4
                            j = i + len - 1
                      
                        5
                            dp[i][j] = INF
                      
                        6
                            for k in i..j-1: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
                      
                        7
                            dp[i][j] += ps[j+1] - ps[i]
                      
                        8
                        return dp[0][n-1]

When to use / Detection cues

  • Input: Adjacent piles.
  • Keywords: merge, combine, minimum cost.
  • Hint: Merge order affects total cost.
  • Core idea: Partition the interval into left and right groups.

For the common merge exactly two adjacent piles version:

dp[i][j]
=
minimum cost to merge i..j into one pile

Java Template

public int mergeStones(int[] stones) {
    int n = stones.length;

    int[] prefix = new int[n + 1];

    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + stones[i];
    }

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

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

            dp[i][j] = Integer.MAX_VALUE;

            for (int k = i; k < j; k++) {
                int cost =
                    dp[i][k]
                    + dp[k + 1][j];

                dp[i][j] =
                    Math.min(dp[i][j], cost);
            }

            dp[i][j] +=
                prefix[j + 1] - prefix[i];
        }
    }

    return dp[0][n - 1];
}
def merge_stones(stones):
    n = len(stones)

    prefix = [0] * (n + 1)

    for i in range(n):
        prefix[i + 1] = prefix[i] + stones[i]

    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            dp[i][j] = float('inf')

            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j]

                dp[i][j] = min(dp[i][j], cost)

            dp[i][j] += prefix[j + 1] - prefix[i]

    return dp[0][n - 1]
int mergeStones(vector<int>& stones) {
    int n = stones.size();

    vector<int> prefix(n + 1);

    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + stones[i];
    }

    vector<vector<int>> dp(n, vector<int>(n));

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

            dp[i][j] = INT_MAX;

            for (int k = i; k < j; k++) {
                int cost =
                    dp[i][k]
                    + dp[k + 1][j];

                dp[i][j] =
                    min(dp[i][j], cost);
            }

            dp[i][j] +=
                prefix[j + 1] - prefix[i];
        }
    }

    return dp[0][n - 1];
}
function mergeStones(stones) {
  const n = stones.length;

  const prefix = new Array(n + 1).fill(0);

  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + stones[i];
  }

  const dp = Array.from({ length: n }, () =>
    new Array(n).fill(0)
  );

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; 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];

        dp[i][j] = Math.min(dp[i][j], cost);
      }

      dp[i][j] += prefix[j + 1] - prefix[i];
    }
  }

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

Note: The LeetCode Merge Stones problem allows merging K piles at once and requires an additional state/dimension. The template above is for the common two-group merge formulation.

Mental trigger

“Merge adjacent groups and cost depends on merge order” → MCM-style DP.

8. Scramble String – Moderate

Scramble String

Can s be transformed into t by recursively swapping children of any node in its split tree?

For substrings s[i..i+len] and t[j..j+len], try every split k: either match directly (s→t both split at k) OR swapped (s left ↔ t right). dp over (start, start, length). O(n⁴) time.

GRID VISUALIZER
Steps –
1
0
1
0
1
0
1
0
1
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        isScramble(i, j, len):
                      
                        2
                          if len == 1: return s[i] == t[j]
                      
                        3
                          for k in 1..len-1:
                      
                        4
                            if (isScramble(i,j,k) && isScramble(i+k,j+k,len-k)) return true
                      
                        5
                            if (isScramble(i,j+len-k,k) && isScramble(i+k,j,len-k)) return true
                      
                        6
                          return false

When to use / Detection cues

  • Input: Two strings.
  • Keywords: scramble, split, rearrange.
  • Hint: Every split creates two possible arrangements.
  • Core idea: Try every split for every substring length.

Unlike normal MCM, this requires an additional dimension for substring length.

State

dp[i][j][len]
=
whether s1[i..i+len-1]
can become
s2[j..j+len-1]

Java Template

public boolean isScramble(String s1, String s2) {
    int n = s1.length();

    if (n != s2.length()) return false;

    boolean[][][] dp =
        new boolean[n][n][n + 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);
        }
    }

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

                for (int k = 1; k < len; k++) {

                    boolean noSwap =
                        dp[i][j][k]
                        &&
                        dp[i + k][j + k][len - k];

                    boolean swap =
                        dp[i][j + len - k][k]
                        &&
                        dp[i + k][j][len - k];

                    if (noSwap || swap) {
                        dp[i][j][len] = true;
                        break;
                    }
                }
            }
        }
    }

    return dp[0][0][n];
}
def is_scramble(s1, s2):
    n = len(s1)

    if n != len(s2):
        return False

    # dp[i][j][length]
    dp = [
        [[False] * (n + 1) for _ in range(n)]
        for _ in range(n)
    ]

    for i in range(n):
        for j in range(n):
            dp[i][j][1] = s1[i] == s2[j]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            for j in range(n - length + 1):

                for k in range(1, length):

                    no_swap = (
                        dp[i][j][k]
                        and dp[i + k][j + k][length - k]
                    )

                    swap = (
                        dp[i][j + length - k][k]
                        and dp[i + k][j][length - k]
                    )

                    if no_swap or swap:
                        dp[i][j][length] = True
                        break

    return dp[0][0][n]
bool isScramble(string& s1, string& s2) {
    int n = s1.size();

    if (n != (int)s2.size()) return false;

    vector<vector<vector<bool>>> dp(
        n,
        vector<vector<bool>>(
            n, vector<bool>(n + 1, false)));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j][1] =
                s1[i] == s2[j];
        }
    }

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

                for (int k = 1; k < len; k++) {

                    bool noSwap =
                        dp[i][j][k]
                        &&
                        dp[i + k][j + k][len - k];

                    bool swap =
                        dp[i][j + len - k][k]
                        &&
                        dp[i + k][j][len - k];

                    if (noSwap || swap) {
                        dp[i][j][len] = true;
                        break;
                    }
                }
            }
        }
    }

    return dp[0][0][n];
}
function isScramble(s1, s2) {
  const n = s1.length;

  if (n !== s2.length) return false;

  const dp = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, () =>
      new Array(n + 1).fill(false)
    )
  );

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      dp[i][j][1] = s1[i] === s2[j];
    }
  }

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len <= n; i++) {
      for (let j = 0; j + len <= n; j++) {
        for (let k = 1; k < len; k++) {
          const noSwap =
            dp[i][j][k] && dp[i + k][j + k][len - k];

          const swap =
            dp[i][j + len - k][k] &&
            dp[i + k][j][len - k];

          if (noSwap || swap) {
            dp[i][j][len] = true;
            break;
          }
        }
      }
    }
  }

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

Mental trigger

“Two strings + recursively split both” → Partition DP with extra state.

9. Expression Evaluation / Different Ways to Add Parentheses – Common

Different Ways to Add Parentheses

All possible results of evaluating an expression with parentheses.

For each operator in a substring, split into left and right, compute all results on both sides, then combine with the operator. dp over substrings; combine result sets. O(n·2ⁿ) in worst case.

GRID VISUALIZER
Steps –
0
1
2
3
1
1
1
2
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        if substring is a number: return [value]
                      
                        2
                        for each operator op at k in substring:
                      
                        3
                          left = solve(i, k-1); right = solve(k+1, j)
                      
                        4
                          for a in left, b in right: push a op b
                      
                        5
                        return results

When to use / Detection cues

  • Input: Arithmetic expression.
  • Keywords: operators, parenthesization, different results.
  • Hint: Each operator can divide the expression.
  • Core idea: Recursively solve left and right expressions.

This is often easier using divide-and-conquer + memoization than a bottom-up table.

Java Template

public List<Integer> diffWaysToCompute(String expression) {
    Map<String, List<Integer>> memo = new HashMap<>();
    return solve(expression, memo);
}

private List<Integer> solve(
        String expression,
        Map<String, List<Integer>> memo) {

    if (memo.containsKey(expression)) {
        return memo.get(expression);
    }

    List<Integer> result = new ArrayList<>();

    for (int i = 0; i < expression.length(); i++) {
        char c = expression.charAt(i);

        if (c == '+' || c == '-' || c == '*') {

            List<Integer> left =
                solve(expression.substring(0, i), memo);

            List<Integer> right =
                solve(expression.substring(i + 1), memo);

            for (int a : left) {
                for (int b : right) {

                    if (c == '+') {
                        result.add(a + b);
                    } else if (c == '-') {
                        result.add(a - b);
                    } else {
                        result.add(a * b);
                    }
                }
            }
        }
    }

    if (result.isEmpty()) {
        result.add(Integer.parseInt(expression));
    }

    memo.put(expression, result);

    return result;
}
def diff_ways_to_compute(expression):
    memo = {}
    return solve(expression, memo)

def solve(expression, memo):
    if expression in memo:
        return memo[expression]

    result = []

    for i in range(len(expression)):
        c = expression[i]

        if c == '+' or c == '-' or c == '*':

            left = solve(expression[:i], memo)

            right = solve(expression[i + 1:], memo)

            for a in left:
                for b in right:

                    if c == '+':
                        result.append(a + b)
                    elif c == '-':
                        result.append(a - b)
                    else:
                        result.append(a * b)

    if not result:
        result.append(int(expression))

    memo[expression] = result

    return result
vector<int> solve(
        string& expression,
        unordered_map<string, vector<int>>& memo) {

    auto it = memo.find(expression);

    if (it != memo.end()) {
        return it->second;
    }

    vector<int> result;

    for (int i = 0; i < (int)expression.size(); i++) {
        char c = expression[i];

        if (c == '+' || c == '-' || c == '*') {

            string leftPart = expression.substr(0, i);
            string rightPart = expression.substr(i + 1);

            vector<int> left = solve(leftPart, memo);

            vector<int> right = solve(rightPart, memo);

            for (int a : left) {
                for (int b : right) {

                    if (c == '+') {
                        result.push_back(a + b);
                    } else if (c == '-') {
                        result.push_back(a - b);
                    } else {
                        result.push_back(a * b);
                    }
                }
            }
        }
    }

    if (result.empty()) {
        result.push_back(stoi(expression));
    }

    memo[expression] = result;

    return result;
}

vector<int> diffWaysToCompute(string expression) {
    unordered_map<string, vector<int>> memo;

    return solve(expression, memo);
}
function diffWaysToCompute(expression) {
  const memo = new Map();
  return solve(expression, memo);
}

function solve(expression, memo) {
  if (memo.has(expression)) {
    return memo.get(expression);
  }

  const result = [];

  for (let i = 0; i < expression.length; i++) {
    const c = expression[i];

    if (c === '+' || c === '-' || c === '*') {
      const left = solve(expression.slice(0, i), memo);

      const right = solve(expression.slice(i + 1), memo);

      for (const a of left) {
        for (const b of right) {
          if (c === '+') {
            result.push(a + b);
          } else if (c === '-') {
            result.push(a - b);
          } else {
            result.push(a * b);
          }
        }
      }
    }
  }

  if (result.length === 0) {
    result.push(parseInt(expression));
  }

  memo.set(expression, result);

  return result;
}

Mental trigger

“Different parenthesizations produce different results” → Split at operators.

10. Polygon Triangulation – Common

Polygon Triangulation

Triangulate a convex polygon to minimize the total triangle weight.

Like MCM: dp[i][j] = min cost to triangulate vertices i..j using a root vertex k forming triangle (i,k,j). Cost = weight[i]·weight[k]·weight[j] + dp[i][k] + dp[k][j]. O(n³) time.

GRID VISUALIZER
Steps –
0
0
6
18
0
0
0
24
0
0
0
0
0
0
0
0
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        for len in 3..n:
                      
                        2
                          for i in 0..n-len:
                      
                        3
                            j = i + len - 1
                      
                        4
                            dp[i][j] = INF
                      
                        5
                            for k in i+1..j-1:
                      
                        6
                              dp[i][j] = min(dp[i][j], w[i]*w[k]*w[j] + dp[i][k] + dp[k][j])
                      
                        7
                        return dp[0][n-1]

When to use / Detection cues

  • Input: Polygon vertices.
  • Keywords: triangulation, minimum score.
  • Hint: Choosing a third vertex creates two smaller polygons.
  • Core idea: Fix endpoints i and j, then choose k.

State

dp[i][j]
=
minimum triangulation score
for polygon section i..j

Transition

dp[i][j] =
min(
    dp[i][k]
    + dp[k][j]
    + value[i] * value[k] * value[j]
)

Java Template

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 + len - 1 < n; i++) {
            int j = i + len - 1;

            dp[i][j] = Integer.MAX_VALUE;

            for (int k = i + 1; k < j; k++) {

                int cost =
                    dp[i][k]
                    + dp[k][j]
                    + values[i]
                    * values[k]
                    * values[j];

                dp[i][j] =
                    Math.min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n - 1];
}
def min_score_triangulation(values):
    n = len(values)

    dp = [[0] * n for _ in range(n)]

    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            dp[i][j] = float('inf')

            for k in range(i + 1, j):
                cost = (
                    dp[i][k]
                    + dp[k][j]
                    + values[i] * values[k] * values[j]
                )

                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]
int minScoreTriangulation(vector<int>& values) {
    int n = values.size();

    vector<vector<int>> dp(n, vector<int>(n));

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

            dp[i][j] = INT_MAX;

            for (int k = i + 1; k < j; k++) {

                int cost =
                    dp[i][k]
                    + dp[k][j]
                    + values[i]
                    * values[k]
                    * values[j];

                dp[i][j] =
                    min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n - 1];
}
function minScoreTriangulation(values) {
  const n = values.length;

  const dp = Array.from({ length: n }, () =>
    new Array(n).fill(0)
  );

  for (let len = 3; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;

      dp[i][j] = Infinity;

      for (let k = i + 1; k < j; k++) {
        const cost =
          dp[i][k] +
          dp[k][j] +
          values[i] * values[k] * values[j];

        dp[i][j] = Math.min(dp[i][j], cost);
      }
    }
  }

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

Mental trigger

“Choose a vertex that splits a polygon” → Interval DP.

General MCM Template

The most important template to memorize is:

public int intervalDP(int[] arr) {
    int n = arr.length;

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

    for (int len = 2; len <= n; len++) {

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

            int j = i + len - 1;

            dp[i][j] = Integer.MAX_VALUE;

            for (int k = i; k < j; k++) {

                int cost =
                    dp[i][k]
                    + dp[k + 1][j]
                    + extraCost(i, k, j);

                dp[i][j] =
                    Math.min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n - 1];
}
def interval_dp(arr):
    n = len(arr)

    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):

        for i in range(n - length + 1):

            j = i + length - 1

            dp[i][j] = float('inf')

            for k in range(i, j):

                cost = (
                    dp[i][k]
                    + dp[k + 1][j]
                    + extra_cost(i, k, j)
                )

                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]
int intervalDP(vector<int>& arr) {
    int n = arr.size();

    vector<vector<int>> dp(n, vector<int>(n));

    for (int len = 2; len <= n; len++) {

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

            int j = i + len - 1;

            dp[i][j] = INT_MAX;

            for (int k = i; k < j; k++) {

                int cost =
                    dp[i][k]
                    + dp[k + 1][j]
                    + extraCost(i, k, j);

                dp[i][j] =
                    min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n - 1];
}
function intervalDP(arr) {
  const n = arr.length;

  const dp = Array.from({ length: n }, () =>
    new Array(n).fill(0)
  );

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; 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] +
          extraCost(i, k, j);

        dp[i][j] = Math.min(dp[i][j], cost);
      }
    }
  }

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

For maximization:

dp[i][j] = Math.max(
    dp[i][j],
    dp[i][k]
    + dp[k + 1][j]
    + extra
);

For counting:

dp[i][j] +=
    dp[i][k]
    * dp[k + 1][j];

For boolean feasibility:

dp[i][j] |=
    dp[i][k]
    && dp[k + 1][j];

Memoization Template

Many MCM problems can first be written recursively and then memoized.

int solve(int i, int j, int[][] dp) {

    if (i >= j) {
        return 0;
    }

    if (dp[i][j] != -1) {
        return dp[i][j];
    }

    int ans = Integer.MAX_VALUE;

    for (int k = i; k < j; k++) {

        int left =
            solve(i, k, dp);

        int right =
            solve(k + 1, j, dp);

        int cost =
            left + right + extraCost(i, k, j);

        ans = Math.min(ans, cost);
    }

    return dp[i][j] = ans;
}
def solve(i, j, dp):

    if i >= j:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    ans = float('inf')

    for k in range(i, j):

        left = solve(i, k, dp)

        right = solve(k + 1, j, dp)

        cost = left + right + extra_cost(i, k, j)

        ans = min(ans, cost)

    dp[i][j] = ans
    return dp[i][j]
int solve(int i, int j, vector<vector<int>>& dp) {

    if (i >= j) {
        return 0;
    }

    if (dp[i][j] != -1) {
        return dp[i][j];
    }

    int ans = INT_MAX;

    for (int k = i; k < j; k++) {

        int left =
            solve(i, k, dp);

        int right =
            solve(k + 1, j, dp);

        int cost =
            left + right + extraCost(i, k, j);

        ans = min(ans, cost);
    }

    return dp[i][j] = ans;
}
function solve(i, j, dp) {
  if (i >= j) {
    return 0;
  }

  if (dp[i][j] !== -1) {
    return dp[i][j];
  }

  let ans = Infinity;

  for (let k = i; k < j; k++) {
    const left = solve(i, k, dp);

    const right = solve(k + 1, j, dp);

    const cost = left + right + extraCost(i, k, j);

    ans = Math.min(ans, cost);
  }

  dp[i][j] = ans;
  return dp[i][j];
}

Why this template is useful

Start with:

recursion
    ↓
memoization
    ↓
tabulation

This makes it easier to derive the transition before worrying about loop order.

How to Identify MCM Problems

Ask:

1. Is the problem defined over a range?

[i ... j]

2. Can I split it somewhere?

[i ... k] + [k+1 ... j]

3. Do I need to try every possible k?

for k = i ... j-1

4. Does the split create independent subproblems?

left + right + current cost

5. Am I minimizing, maximizing, counting, or checking?

If most answers are yes:

Think MCM / Partition DP.

Recognition Cheat Sheet

If you see…Think…
Different multiplication ordersMatrix Chain Multiplication
Minimum palindrome cutsPalindrome Partitioning
Cutting a segmentMinimum Cost to Cut Stick
Removal order affects scoreBurst Balloons
Count true/false evaluationsBoolean Parenthesization
Choose optimal BST rootOptimal BST
Merge adjacent groupsMerge Stones
Recursively split two stringsScramble String
Parenthesize expressionsExpression DP
Partition polygonPolygon Triangulation

Complexity Pattern

For standard interval DP:

States:
O(n²)

Transitions:
O(n)

Total:
O(n³)

Space:
O(n²)

Some variations require more:

Boolean Parenthesization:
O(n³)

Scramble String:
O(n⁴)

Remove Boxes:
O(n⁴) states/transitions depending on implementation

Common Mistakes

1. Using the wrong interval

Always clarify:

dp[i][j]

Does it mean:

i through j inclusive?

Usually yes.

2. Wrong split boundary

For:

dp[i][j]

the standard split is:

[i ... k]
[k+1 ... j]

So:

for (int k = i; k < j; k++)

3. Filling intervals in the wrong order

Smaller intervals must already be calculated.

Use:

for (int len = 2; len <= n; len++)

4. Forgetting base cases

For many MCM problems:

if (i >= j) return 0;

because a single element cannot be partitioned further.

5. Choosing the first operation when the state is difficult

For removal problems such as Burst Balloons:

Choosing first → difficult neighbors

Choosing last → fixed neighbors

Mental trick:

If removing something changes its neighbors, try choosing the last operation.

MCM vs Other DP Patterns

Problem ShapePattern
dp[i]1D DP
dp[i][j] comparing two strings2D String DP
dp[i][j] representing a rangeInterval DP
dp[i][j] + try every kMCM / Partition DP
dp[i][j][state]Interval DP + extra state
Grid coordinatesGrid DP
Take/skip itemsKnapsack DP
Increasing subsequenceLIS DP

My Private Notes

Notes are auto-saved locally to this device.