📜 WAYPOINT LESSON
Split Points
⭐⭐⭐ advanced⏳ 30 min read📍 Lesson 161 of 281
Interval DP grows answers from length-1 ranges outward; every split point k combines dp[i][k] with dp[k+1][j].
From short intervals to long
dp[i][j] = best answer for the interval i..j. The recurrence tries every split k: dp[i][k] + dp[k+1][j] + merge_cost. Loop interval LENGTHS first, then start positions — that guarantees sub-intervals are ready before the intervals that need them. Matrix-chain is the canonical example.