Burst Balloons — Interval DP Reversed

The twist

Naive forward DP is hard: bursting changes neighbors. Instead: think in reverse. Which balloon burst LAST in a range?

State

dp[i][j] = max coins from bursting balloons strictly between i and j (exclusive).

Transition

for (int len = 2; len <= n+1; len++)
  for (int i = 0; i + len <= n+1; i++) {
    int j = i + len;
    for (int k = i+1; k < j; k++)
      dp[i][j] = max(dp[i][j],
        dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]);
  }

Ghost balloons

Pad with 1s at both ends: [1, ...nums..., 1]. Simplifies boundary logic.