Partition DP
Matrix-chain multiplication and palindrome partitioning ask: where do I split? Try every cut and keep the best.
The problem
You need to multiply a chain of matrices: A(10×30) · B(30×5) · C(5×60). Matrix multiplication
is associative, so the result is the same however you parenthesize — but the cost is not.
Doing (AB)C takes 10·30·5 + 10·5·60 = 4500 scalar multiplications; A(BC) takes
30·5·60 + 10·30·60 = 27000. Same answer, six times the work.
With three matrices you can try both groupings by hand. With twenty, the number of parenthesizations is astronomical. The question underneath is always the same: where do you place the split? And the same question drives palindrome partitioning, burst balloons, and optimal binary search trees.
A first attempt
Try every possible outermost split. For the range of matrices i..j, pick a split point k,
recursively solve i..k and k+1..j, and add the cost of combining the two halves.
def matrix_chain(dims, i, j):
if i == j:
return 0
best = float('inf')
for k in range(i, j):
cost = (matrix_chain(dims, i, k)
+ matrix_chain(dims, k + 1, j)
+ dims[i - 1] * dims[k] * dims[j])
best = min(best, cost)
return bestEvery range spawns a split at each interior point, and those subranges overlap massively — the
recursion is exponential. But a subproblem is fully described by its endpoints (i, j), and
there are only about n² of those.
The insight
The state is an interval, and you decide where to cut it:
dp[i][j]= the best cost to fully process the rangei..j. Compute it by trying every split pointkinside the range, combining the already-solved left and right pieces.
The defining feature of partition DP is the order of evaluation. A range depends on shorter ranges, so you must fill the table by increasing interval length, not by row or column.
solve length-1 ranges first (base cases)
then length-2, length-3, ... up to the full range
each dp[i][j] = min over k of ( dp[i][k] + dp[k+1][j] + join cost )How it works
Define the interval state
dp[i][j] = the optimal cost (or count) for the subarray from i to j inclusive. The final
answer is dp[0][n-1] (or dp[1][n] for matrix chain, depending on indexing).
Base case: trivial intervals
A single element needs no work: dp[i][i] = 0. For matrix chain a single matrix costs nothing;
for palindrome partitioning a single character needs no cut.
Try every split
For range i..j, loop k from i to j-1. Each k divides the range into i..k and
k+1..j, both already solved. Combine them with the problem's join cost and keep the best.
Iterate by increasing length
Loop over interval length from 2 up to n, and for each length slide the window across all
valid (i, j). This guarantees every sub-interval you read is already filled.
The code
Matrix-chain multiplication. dims has length n+1; matrix m is dims[m-1] × dims[m].
def matrix_chain(dims):
n = len(dims) - 1 # number of matrices
dp = [[0] * (n + 1) for _ in range(n + 1)]
for length in range(2, n + 1): # interval length
for i in range(1, n - length + 2):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j): # split point
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 matrixChain(dims: number[]): number {
const n = dims.length - 1;
const dp = Array.from({ length: n + 1 }, () => new Array<number>(n + 1).fill(0));
for (let length = 2; length <= n; length++) {
for (let i = 1; i + length - 1 <= n; 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] + dims[i - 1] * dims[k] * dims[j];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
return dp[1][n];
}class Solution {
int matrixChain(int[] dims) {
int n = dims.length - 1;
int[][] dp = new int[n + 1][n + 1];
for (int length = 2; length <= n; length++) {
for (int i = 1; i + length - 1 <= n; i++) {
int j = i + length - 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];
}
}#include <limits.h>
int matrix_chain(int *dims, int len) {
int n = len - 1;
int dp[n + 1][n + 1];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++) dp[i][j] = 0;
for (int length = 2; length <= n; length++) {
for (int i = 1; i + length - 1 <= n; i++) {
int j = i + length - 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];
if (cost < dp[i][j]) dp[i][j] = cost;
}
}
}
return dp[1][n];
}int matrixChain(vector<int> &dims) {
int n = dims.size() - 1;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int length = 2; length <= n; length++) {
for (int i = 1; i + length - 1 <= n; i++) {
int j = i + length - 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];
}Complexity
| Approach | Time | Space |
|---|---|---|
| Naive recursion | Exponential | O(n) stack |
| Interval DP | O(n³) | O(n²) |
There are O(n²) intervals, and each tries up to O(n) split points, so the total is O(n³). Space is the O(n²) table of intervals.
When to use it
The tell: 'where do I split?'
Reach for partition DP when the answer over a range is built by choosing a split point and combining two sub-ranges — matrix chain, palindrome partitioning, burst balloons, optimal BST, boolean parenthesization. The non-negotiable detail is filling the table by increasing interval length so every sub-range is ready before you use it.
Practice
Recap
- Partition DP solves problems by asking where to cut a range and combining the two halves.
- The state is an interval
dp[i][j]; you try every split pointkinside it. - Fill the table by increasing interval length; the classic cost is O(n³) over O(n²) intervals.
How is this guide?
Last updated on