LeetCode 312 Burst Balloons - Walkthrough

Pop balloons to find the largest coins. Array $[3, 1, 5, 8]$. Add virtual 1s at ends: $[1, 3, 1, 5, 8, 1]$. The trick: instead of "which to pop first", think "which to pop last in interval". $dp[i][j]$ = max coins from popping all balloons in $(i, j)$ exclusive, assuming $i$ and $j$ are still there.

For interval $(0, 5)$ (all real balloons): try each as last. If $3$ is last: $dp[0][1] + dp[1][5] + 1 \cdot 3 \cdot 1 = 0 + \ldots + 3$. Compute recursively.