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.
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)
