Burst Balloons

GIVEN: n balloons, indexed from 0 to n — 1.

Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons..

If you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. That is the product of the three balloons centered at i, which nums[left] or nums[right] leaves unchanged, like multiplying by 1, if left or right is out of bounds. Here left and right are adjacent indices of i; if left and right are out of bounds, you will get nums[i] coins.

After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect, by bursting the balloons wisely.

The idea is that we are given n balloons and can return the maximum number of coins we can collect, wisely.¹

APPROACH (dynamic programming, top-down):

The best score after adding the ith balloon is given by:

nums[left] * nums[i] * nums[right]
     + dp(left, i)
     + dp(i, right)

Define a function dp to return the maximum number of coins obtainable on the open interval (left, right). Our base case is if there are no integers on our interval. This occurs when left + 1 == right and ∴ no more balloons can be added. Yes, this can be done.²

var maxCoins = function(nums) {
     let n = nums.length + 2;
     let new_nums = new Array(n);

for (let i = 0; i < nums.length; i++) {
          new_nums[i+1] = nums[i];
     };
     new_nums[0] = new_nums[n-1] = 1;
     let memo = new Map();
     for (let i = 0; i < n; i++) {
          memo[i] = new Map();
     }
     return dp(memo, new_nums, 0, n - 1);
};

If you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. This presupposes that nums[left] and nums[right] always exist. So, reframe the problem. Nums -> new_nums. (Because we can only burst balloons which are not on the edge of the nums array, we append the number 1 on each side of the nums array). Now, here’s the real function.³

var dp = function(memo, nums, left, right) {
     if (left + 1 == right) { return 0; }
     if (memo[left][right] > 0) {
          return memo[left][right];
     }
     let ans = 0;
     for (let i = left + 1; i < right; ++i) {
          ans = Math.max(
               ans, nums[left] * nums[i] * nums[right]
               + dp(memo, nums, left, i)
               + dp(memo, nums, i, right)
          );
     };
     memo[left][right] = ans;
     return ans;
}

If nums[left] and nums[right] are adjacent, then return 0 because no more balloons can be added. Then, check the cache. The time complexity, because we determine the maximum score over all (left, right) pairs requiring adding all balloons within the interval [left, right], giving O(N²) * O(N), is O(N³). The space complexity is O(N²), because our dp function requires and so expects the space N×N for cache memo, which is N×N.⁴

memo is created as follows. Let’s say we’re given nums = [3, 1, 5, 8]. Then, memo resolves into

Map(0) {
     '0': Map(0) { '2': 3, '3': 30, '4': 159, '5': 167 },
     '1': Map(0) { '3': 15, '4': 135, '5': 159 },
     '2': Map(0) { '4': 40, '5': 48 },
     '3': Map(0) { '5': 40 },
     '4': Map(0) {}, 
     '5': Map(0) {}
 }

Recall that when we pop a balloon at index i, memo[i-1][i+1] is the current, cumulative number of coins.

Adding 1 on each side, new_nums = [1,3,1,5,8,1].

The array is [1, 3, 1, 5, 8, 1],

the indices are 0, 1, 2, 3, 4, 5.

Pop the balloon at index 2, which has a value of 1 →

coins = new_nums[left]*new_nums[2]*new_nums[right]

= 3*1*5

= 15.

And memo[1][3] = 15.

The array is [1, 3, 5, 8, 1].

the indices are 0, 1, 3, 4, 5.

Pop the balloon at index 3, which has a value of 5 →

coins = previous value + 
        new_nums[left] * new_nums[3] * new_nums[right]
 = 15 + 3*5*8
 = 135.

And memo[left][right] == memo[1][4] = 135.

The array is [1, 3, 8, 1].

the indices are 0, 1, 4, 5.

Pop the balloon at index 1, which has a value of 3 →

coins = previous value + 
        new_nums[left] * new_nums[1] * new_nums[right]
 135 + 1*3*8
 = 159.

And memo[left][right] == memo[0][4] = 159.

The array is [1, 8, 1].

The indices are 0, 4, 5.

Pop the balloon at index 4, which has a value of 8 →

coins = previous value + 
        new_nums[left] * new_nums[4] * new_nums[right]
 = 159 + 1*8*1
 = 167.

And memo[left][right] == memo[0][5] = 167.

Memo stores all the results, and we are taking the maximum of all results.

dp will store the results of our calls. Define dp the Map:

var maxCoins = function(nums) {
     let n = nums.length + 2;
     let new_nums = new Array(n);
     for (let i = 0; i < nums.length; i++) {
          new_nums[i+1] = nums[i];
     }
     new_nums[0] = new_nums[n-1] = 1;
     let dp = new Map();
     for (let i = 0; i < n; i++) {
          dp[i] = new Map();
          for (let j = 0; j < n; j++) {
               dp[i][j] = 0;
          }
     }
     for (let left = n - 2; left > -1; left--) {
          for (let right = left + 2; right < n; right++) {
               for (let i = left + 1; i < right; ++i) {
                    dp[left][right] = Math.max(
                         dp[left][right], 
                         new_nums[left] * new_nums[i] * new_nums[right] + 
                         dp[left][i] + 
                         dp[i][right]
                    );
               }
          }
     }
     return dp[0][n-1];
}

dp resolves into

Map(0) {
     '0': Map(0) { '0': 0, '1': 0, '2': 3, '3': 30, '4': 159, '5': 167 },
     '1': Map(0) { '0': 0, '1': 0, '2': 0, '3': 15, '4': 135, '5': 159 },
     '2': Map(0) { '0': 0, '1': 0, '2': 0, '3': 0, '4': 40, '5': 48 },
     '3': Map(0) { '0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 40 },
     '4': Map(0) { '0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0 }, 
     '5': Map(0) { '0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0 }
 }

.

[1]: Burst Balloons — LeetCode
https://leetcode.com/problems/burst-balloons/

[2]: 312. Burst Ballons — Problem Solving with Algorithms
https://inner-game.tistory.com/402

[3]: 算法打卡第四天 — 掘金
https://juejin.cn/post/7054070442071425037

[4]: LeetCode — Burst Balloons
https://gist.github.com/cangoal/4104223f9837337a1acf193e31a09c84