LeetCode 312 Burst Balloons - Problem Statement

You have $n$ balloons with numbers on them. Bursting balloon i gives you $nums[i-1] \times nums[i] \times nums[i+1]$ coins. After bursting, the neighbors become adjacent. Find the maximum coins you can collect by bursting all balloons in the optimal order.

This looks like you could pick the locally best choice each time, but that approach fails. The order matters because bursting changes the neighbors. This is interval DP in disguise.