DiffPush Tier Dynamic Programming · DP on Partition O(n^3) · O(n^2)
A festival crew detonates a line of celebratory charges, each stamped with a potency number. Detonating a charge scores the product of its potency with its two current neighbors, and neighbors close ranks after each blast. Boundary positions pair with a fixed neutral value of 1. The pyrotechnician chooses the firing order to maximize the evening's total score.
Input: An array nums of n balloon values.
Output: Return the maximum coins collectable by bursting every balloon, scoring nums[i-1] * nums[i] * nums[i+1] per burst with virtual 1s at the ends.
1 <= n <= 3000 <= nums[i] <= 100Input: {"nums":[3,1,5,8]}
Output: 167
Burst order 1, 5, 3, 8 scores 15 + 120 + 24 + 8 = 167 in total.
Input: {"nums":[1,5]}
Output: 10
Burst 1 first (1*5*1 = 5), then 5 (1*5*1 = 5) — total 10; bursting 5 first only reaches 6.