Balloons padded with 1 at both ends · yellow = interval (l, r) · blue = k, burst last · outlined = its neighbours then
dp cell (l, r) = most coins from bursting balloons l..r while l−1 and r+1 still stand
Call stack bottom → top
private int[] nums;private Integer[][] dp;public int maxCoins(int[] input) { int n = input.length; nums = new int[n + 2]; nums[0] = 1; nums[n + 1] = 1; System.arraycopy(input, 0, nums, 1, n); dp = new Integer[n + 2][n + 2]; return dfs(1, nums.length - 2);}private int dfs(int l, int r) { if (l > r) { return 0; } if (dp[l][r] != null) { return dp[l][r]; } dp[l][r] = 0; for (int i = l; i <= r; i++) { // i bursts last int coins = nums[l - 1] * nums[i] * nums[r + 1]; coins += dfs(l, i - 1) + dfs(i + 1, r); dp[l][r] = Math.max(dp[l][r], coins); } return dp[l][r];}
- l, r
- —
- i (k)
- —
- coins
- —
- dp[l][r]
- —
- memo hits
- 0
Why it works
- Brute force tries every burst order: n! of them. Choosing which balloon to burst first does not split the problem, because its neighbours change and the two sides keep interacting.
- Choose the one burst last instead. If balloon
kis the last one popped in(l, r), then when it pops its neighbours are exactlyl−1andr+1, which are outside the interval and still standing. Everything left ofkand right ofkwas popped earlier, independently, withkas a fixed wall:dp(l, r) = max over k of nums[l−1]·nums[k]·nums[r+1] + dp(l, k−1) + dp(k+1, r). - Complexity: O(n²) intervals, each tries O(n) choices of
k: O(n³) time, O(n²) space. - Pitfall: pad with a 1 at each end so the edge balloons have neighbours, and use the interval's outer neighbours
nums[l−1]andnums[r+1], notnums[k−1]andnums[k+1]: those are long gone whenkpops last. - Bottom-up: fill the same table by interval length, short to long, so both halves are always ready. Related interval DPs: Minimum Cost to Cut a Stick (1547), Matrix Chain Multiplication.