Leetcode 312. Burst Balloons

Given an array of balloon values, find the maximum coins you can collect by bursting balloons optimally. When you burst balloon at index i, you gain coins equal to nums[i-1] * nums[i] * nums[i+1] (treat out-of-bounds as 1). Return the maximum total coins obtainable. The reward depends on dynamic neighbors, so the core challenge is exploiting optimal substructure (interval/segment DP over subarrays) to find the best bursting sequence for n up to 300.