Burst Balloons: why does DP over intervals (not balloons) work?

Question presented to candidate: "You have n balloons in a row, each with a number. Bursting balloon i earns left × nums[i] × right, where left and right are its current neighbours (a missing neighbour counts as 1). Find the maximum coins. Code it in Python, and explain why the DP is over intervals and why you choose the balloon burst last rather than first."

What a strong answer should cover:

• Why "choose the first balloon" fails: its neighbours become adjacent, so the two sides are not independent sub-problems.
• The insight: choose the balloon k burst last in the open interval (i, j); it separates the two sides, and its neighbours are fixed as a[i] and a[j].
• Padding with 1s, the state dp[i][j], the recurrence max(dp[i][k] + a[i]·a[k]·a[j] + dp[k][j]), and filling by interval length.
• O(n³) time and O(n²) space versus O(n · n!) for trying every order.
• Python details: build the 2-D table with a comprehension (never [[0] * n] * n), pad with [1] + nums + [1], and know that a top-down @lru_cache version is short but pays recursion and call overhead; ints never overflow.

Clarifying questions expected:

• What does a missing neighbour count as, and how large are n and the values?
• Do you need the burst order, or only the maximum?

Code / implementation expected: Yes — max_coins(nums) in Python with a padded list and an O(n³) interval table.