Interval DP
dp over a range with a split point inside it. Iterate by increasing length so smaller ranges are ready.
Dynamic ProgrammingO(n^3)New8 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
matrix chain multiplication
burst balloons
palindrome partitioning
stone game
The template
Get this into muscle memory, then adapt the condition per problem.
for (let len = 2; len <= n; len++)
for (let i = 0; i + len <= n; i++) {
const j = i + len - 1;
for (let k = i; k < j; k++)
dp[i][j] = best(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, k, j));
}If you are stuck
The generic hint ladder for this pattern, in order.
- 1The answer for a range depends on how you split it.
- 2Think about which element you handle last, not first.
- 3Order the loops by range length so dependencies are already computed.
Drill it
Every problem in the bank that uses this pattern.
0 / 8 solved