Solve problems on segments by building answers from small intervals up to the entire array.
Sometimes, the state isn't just an index, but a range: [start, end]. This happens in problems where you merge adjacent items (like Bursting Balloons or Matrix Chain Multiplication).
To solve the range [i, j], you guess the last operation that happens. This splits the range at some point k. So, the cost is the cost of the left piece [i, k] plus the right piece [k+1, j] plus the cost of merging them. Because larger intervals depend on smaller ones, we fill the DP table ordered by length of the interval, from 1 up to N.
def matrixChainOrder(p):
n = len(p) - 1
dp = [[0] * n for _ in range(n)]
# Fill by length L
for L in range(2, n + 1):
for i in range(n - L + 1):
j = i + L - 1
dp[i][j] = float('inf')
# Try every split point k
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]
dp[i][j] = min(dp[i][j], cost)
return dp[0][n-1]