DP on intervals by choosing the last/first action inside a range
Define dp[l][r] and split at k in (l..r); often think 'burst last' to fix boundaries.
Use when subproblems are contiguous ranges and choices partition the interval.
dp[l][r] over increasing lengths; choose split k in (l..r) to combine subranges (e.g., matrix chain, burst balloons).
# Bitmask DP Template (TSP)
def tsp(dist):
n=len(dist); INF=10**9
dp=[[INF]*(1<<n) for _ in range(n)]
dp[0][1]=0
for mask in range(1<<n):
for u in range(n):
if not (mask>>u)&1: continue
d=dp[u][mask]
if d==INF: continue
for v in range(n):
if (mask>>v)&1: continue
nm=mask|1<<v
dp[v][nm]=min(dp[v][nm], d+dist[u][v])
return min(dp[u][(1<<n)-1]+dist[u][0] for u in range(n))Burst last to fix neighbors
def burst_balloons(nums):
nums=[1]+nums+[1]; n=len(nums)
dp=[[0]*n for _ in range(n)]
for len_ in range(2, n):
for l in range(0, n-len_):
r=l+len_
for k in range(l+1, r):
dp[l][r]=max(dp[l][r], nums[l]*nums[k]*nums[r]+dp[l][k]+dp[k][r])
return dp[0][n-1]Parenthesize to minimize multiplications
def matrix_chain(dims):
n=len(dims)-1; dp=[[0]*n for _ in range(n)]
for len_ in range(2, n+1):
for l in range(0, n-len_+1):
r=l+len_-1; dp[l][r]=10**18
for k in range(l, r):
dp[l][r]=min(dp[l][r], dp[l][k]+dp[k+1][r]+dims[l]*dims[k+1]*dims[r+1])
return dp[0][n-1]Merge cost with window sizes
def merge_stones(stones, K):
n=len(stones); INF=10**18
if (n-1)%(K-1)!=0: return -1
pref=[0];
for x in stones: pref.append(pref[-1]+x)
dp=[[0]*n for _ in range(n)]
for len_ in range(K, n+1):
for l in range(0, n-len_+1):
r=l+len_-1; dp[l][r]=INF
for m in range(l, r, K-1):
dp[l][r]=min(dp[l][r], dp[l][m]+dp[m+1][r])
if (len_-1)%(K-1)==0:
dp[l][r]+= pref[r+1]-pref[l]
return dp[0][n-1]Split over k for each interval.
2D DP table.