Interval DP: choose the last balloon to burst in each interval.
Pad with 1s: a = [1] + nums + [1].
Let dp[l][r] = max coins from bursting balloons strictly between indices (l, r).
Pick last burst k in (l,r):
dp[l][r] = max(a[l]*a[k]*a[r] + dp[l][k] + dp[k][r]).
Compute by increasing interval length.
Interval DP: choose the last balloon to burst in each interval.
Pad with 1s: a = [1] + nums + [1].
Let dp[l][r] = max coins from bursting balloons strictly between indices (l, r).
Pick last burst k in (l,r):
dp[l][r] = max(a[l]*a[k]*a[r] + dp[l][k] + dp[k][r]).
Compute by increasing interval length.