LeetCode 312 Burst Balloons - The Trick

Here's the observation: instead of thinking which balloon to burst first, think about which balloon to burst LAST in a range. Why? When you burst balloon k last in range $[i,j]$, you know exactly what neighbors k has: the balloons at i-1 and j+1 (outside the range). The balloons inside $[i,j]$ are already gone.

This eliminates the dependency problem. The coins from bursting k last = $nums[i-1] \times nums[k] \times nums[j+1]$ + coins from $[i,k-1]$ + coins from $[k+1,j]$.