Working out the cheapest way to multiply a chain of matrices by trying every place to put the last bracket.
Clues that point here
→ Answer for a range depends on how you split it
→ Burst balloons, matrix chain multiplication
→ Palindromic substrings and partitions
→ Merge stones
Not this pattern when
✕ The split point is always the same (simpler DP)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Interval DP · template
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = baseOrInfinity(i, j);
for (int k = i; k < j; k++) {
dp[i][j] = best(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i, k, j));
}
}
}
return dp[0][n - 1];