LeetCode. 312. Burst Balloons

Problem

Interval dynamic programming

Add a virtual balloon with value 1 at each end of the array. Let dp[l][r] be the maximum coins obtainable by bursting every balloon strictly between boundaries l and r, while leaving those two boundary balloons unburst.

Choose the last balloon k to burst in that open interval. At that moment, all other balloons inside the interval are already gone, so its neighbors are exactly l and r. The final burst earns values[l] * values[k] * values[r]; the balloons on either side were burst earlier and contribute the independently optimal subproblems dp[l][k] and dp[k][r]. Thus:

dp[l][r] = max(dp[l][k] + values[l] * values[k] * values[r] + dp[k][r])

for l < k < r. Evaluate intervals in increasing width so both smaller intervals have already been computed. With n original balloons there are O(n^2) intervals and up to O(n) choices of k per interval, giving O(n^3) time and O(n^2) space. An empty input has no interior balloons, so the answer is zero.

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] values = new int[n + 2];
        values[0] = values[n + 1] = 1;
        for (int i = 0; i < n; i++) {
            values[i + 1] = nums[i];
        }

        int[][] dp = new int[n + 2][n + 2];
        for (int width = 2; width < n + 2; width++) {
            for (int left = 0; left + width < n + 2; left++) {
                int right = left + width;
                for (int last = left + 1; last < right; last++) {
                    int coins = dp[left][last]
                            + values[left] * values[last] * values[right]
                            + dp[last][right];
                    dp[left][right] = Math.max(dp[left][right], coins);
                }
            }
        }

        return dp[0][n + 1];
    }
}