Interval DP Pattern and Fill Order
Define the interval DP state dp[i][j], explain why intervals must be filled in increasing length order, and trace the pattern on matrix chain multiplication.
What Is Interval DP?
Interval DP is a dynamic programming pattern where the state dp[i][j] represents the optimal answer for the sub-problem spanning indices i through j. The key insight is that we solve smaller intervals first and build up to the full range. This pattern naturally models problems like matrix chain multiplication, palindrome partitioning, and balloon bursting, where the sub-problem boundaries are the left and right endpoints of a range.
State Definition and Base Cases
For interval DP, the state is dp[i][j] where i <= j. The base cases are single-element intervals: dp[i][i]. These are trivially solved — for example, a single matrix has zero multiplication cost. Two-element intervals dp[i][i+1] often have simple answers too. We fill the table for increasing interval lengths, starting from length 1 up to n.
n = 4
dp = [[0] * n for _ in range(n)]
# Base cases: single elements
for i in range(n):
dp[i][i] = 0 # length-1 intervalsAll lessons in this course
- Interval DP Pattern and Fill Order
- Longest Palindromic Subsequence and Substring
- Palindrome Partitioning II
- Burst Balloons: Reverse Interval DP