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 , you know exactly what neighbors k has: the balloons at i-1 and j+1 (outside the range). The balloons inside are already gone.
This eliminates the dependency problem. The coins from bursting k last = + coins from + coins from .