Hints — p71 Burst Balloons

Hint 1. Brute force is permutations of burst orders, O(n!). For n=500 (LC constraint), you need DP. Recognize: interval DP.

Hint 2. Naive interval DP — “let dp[i][j] = max coins from interval [i,j], enumerate the FIRST balloon k to burst” — FAILS. Why? When k bursts first, its neighbors are whatever’s left in [i,j], not the original endpoints. Subproblems aren’t independent.

Hint 3. Flip the decomposition: enumerate the LAST balloon to burst in (i,j). When k is the LAST one remaining in (i,j) before bursting, everything else in (i,j) is already gone, so k’s neighbors at burst time are exactly i and j. Clean.

Hint 4. Pad nums with 1 on each end (sentinel). Define dp[i][j] = max coins from bursting balloons STRICTLY between i and j. Recurrence:

dp[i][j] = max over k in (i,j) of:
    nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]

Hint 5. Fill order: by increasing interval length (j - i). This ensures dp[i][k] and dp[k][j] are computed before dp[i][j]. O(n³) time, O(n²) space. Answer: dp[0][n+1] after padding.

If stuck: see solution.py.