Burst Balloons

Question (LC.312)

Given n balloons b_0, b_1, ..., b_{n-1}, each balloon contains a number of coins. The player needs to shoot all balloons and maximize her score. The score from each balloon will be coins[i-1] * coins[i] * coins[i+1]. After b_i is getting shot, b_{i-1} and b_{i+1} bocome adjacent to each other.

Example

I: []
O: 0
I: [3,1,5]
O: shoot 1 (3*1*5) + shoot 3 (3*5) + shoot 5 (5) = 15 + 15 + 5 = 35 
I: [5,4,3,2,10]
O: 440

Brute Force Search

We can do a brute force search by trying every possible bursts and return a maximum. Then, we observe the fact that there are overlapping subproblems. We can add in a cache mechanism to speed it up.

But we can't quite find a way to do a full DP because we can't define a subproblem that can be represented by indices.

Cached Brute Force

public int maxCoins(int[] coins) {
    // sanity check
    if (coins == null || coins.length == 0) {
        return 0;
    }
    int n = coins.length; // labels are from 0 to n-1
    List<Integer> coinList = new ArrayList<>();
    for (int coin : coins) {
        coinList.add(coin);
    }
    // init memo
    Map<List<Integer>, Integer> cache = new HashMap<>();
    // topo order
    return balloonHelper(cache, coinList);
}   

private int balloonHelper(Map<List<Integer>, Integer> cache, List<Integer> coinList) {
    // base cases 1. one element 2. memoized
    if (cache.containsKey(coinList)) {
        return cache.get(coinList).intValue();
    }
    if (coinList.size() == 1) {
        return coinList.get(0).intValue();
    }
    // recursive calls
    int maxCoins = 0;
    for (int i = 0; i < coinList.size(); i++) {
        // compute burst value
        int burstValue = coinList.get(i).intValue();
        if (i - 1 >= 0) burstValue *= coinList.get(i - 1).intValue();
        if (i + 1 < coinList.size())burstValue *= coinList.get(i + 1).intValue();
        // backtracking
        Integer coin = coinList.remove(i);
        maxCoins = Math.max(maxCoins, burstValue + balloonHelper(cache, coinList));
        coinList.add(i, coin);
    }
    // memoize
    if (!cache.containsKey(coinList)) {
        cache.put(coinList, maxCoins);
    }
    return maxCoins;
}

The state representation is very inefficient here (adding and removing coins from the list are very costly operations). A simple test case [8,2,6,8,9,8,1,4,1,5,3,0,7,7,0,4,2,2,5,5] will exceed the time limit on LC.

Note: Using mutable objects as hashing key can be very dangerous. When the input size gets large enough, there will be collisions and wrong returning values.

Redefine Subproblem

The way we defined the state previous is by thinking on the first balloon that we want to burst. Let's try another way to define the state in a bottom-up fashion. What is the last balloon that we want to burst?

Before:
for i from 1 to len(coinList)
    burstValue = coinList[i-1] * coinList[i] * coinList[i+1]
    maxCoins[coinList] = max(burstValue + maxCoins[coinList.remove(i)])

Now:
for k from start to end
    // saved balloon on the left * current last balloon * saved balloon on the right
    burstValue = coins[start-1] * coins[k] * coins[end+1] 
    // maxCoins(coins[start:end]) is represented by state maxCoins[start][end]
    maxCoins[start][end] = max(burstValue + maxCoins[start][k-1] + maxCoins[k+1][end])

Cached Interval Search

public int maxCoins(int[] coins) {  
    // sanity check
    if (coins == null || coins.length == 0) {
        return 0;
    }
    // pad 1 on left and right (since this is the first level)
    int[] coins2 = new int[coins.length + 2];
    coins2[0] = 1;
    coins2[coins2.length -1] = 1;
    for (int i = 0; i < coins.length; i++) {
        coins2[i+1] = coins[i];
    }
    // init memo
    int[][] cache = new int[coins2.length][coins2.length];
    boolean[][] cached = new boolean[coins2.length][coins2.length];
    // memoized search
    return coinHelper2(cache, cached, coins2, 1, coins2.length - 2);
}

private int coinHelper2(int[][] cache, boolean[][] cached, int[] coins2, int start, int end) {
    // base cases
    if (start > end) {
        return 0;
    }
    if (cached[start][end]) {
        return cache[start][end];
    }
    // recursive calls
    int maxCoins = 0;
    for (int k = start; k <= end; k++) {
        int burstValue = coins2[start-1] * coins2[k] * coins2[end+1];
        int leftInterval = coinHelper2(cache, cached, coins2, start, k-1);
        int rightInterval = coinHelper2(cache, cached, coins2, k+1, end);
        maxCoins = Math.max(maxCoins, burstValue + leftInterval + rightInterval);               
    }
    // memoize
    cache[start][end] = maxCoins;
    cached[start][end] = true;

    return maxCoins;
}

Bottom Up Interval DP

This is an optimization problem with a single sequence. Since each decision depends on left and right, the state needs to be defined by substrings or intervals. Prefix or suffix will not be a suffient representation when breaking down the current problem into subproblems.

1. Define Optimal Subproblem
    BL[i][j] = the maximal points one can get in the interval coins[i:j]

2. Solve by Substring
    for k from i to j
        last_shot = coins[i-1] * coins[k] * coins[j+1]
        points = BL[i][k-1] + BL[k+1][j] + last_shot
        BL[i][j] = max(BL[i][j], points)

3. Init Base
    We are only comparing the max points. Starting off 0s for all intervals will be fine.

4. Topo Order
    Enumerating all substrings from small to large to make sure all dependencies are satisfied.
    i.e. BL[i][k-1] and BL[k+1][j] need to be computed before we get to BL[i][j]

    for size from 1 to n
        for start from 0 to (n-1) - size + 1 // +1 to include the start element
            end = start + size - 1 // -1 because size includes the start element
            // solve by substring

5. Final Answer
    BL[0][n-1]

DP Code

public int maxCoins(int[] coins) {
    // safety check
    if (coins == null || coins.length == 0) {
        return 0;
    }
    // pad 1 on left and right
    int[] coins2 = new int[coins.length + 2];
    coins2[0] = 1;
    coins2[coins2.length - 1] = 1;
    for (int i = 0; i < coins.length; i++) coins2[i+1] = coins[i];
    // create memo table
    int n = coins2.length;
    int[][] memo = new int[n][n];
    // init base cases (0 for all intervals)
    // topo order
    for (int size = 1; size <= n - 2; size++) {
        for (int start = 1; start <= (n-2) - size + 1; start++) {
            int end = start + size - 1;
            for (int k = start; k <= end; k++) {
                int lastShot = coins2[start - 1] * coins2[k] * coins2[end + 1];
                int points = memo[start][k-1] + memo[k+1][end] + lastShot;
                memo[start][end] = Math.max(memo[start][end], points);                
            }
        }
    }
    // final answer
    return memo[1][n-2];
}

Time & Space Complexity

Time = #subproblems * time/subproblem 
     = O(n^2) (all substrings) * O(n) (worst case enumerate all partitions) 
     = O(n^3)
Space = O(n^2)