Practice › Dynamic Programming
Burst Balloons
Hard · Dynamic Programming · Asked at Google, Amazon, Microsoft, Snapchat
Bursting balloon i earns left · a[i] · right, where left and right are the values of its current neighbours (a missing neighbour counts as 1); the burst balloon then disappears. Burst all balloons and print the maximum total coins.
Input
First line: n. Second line: n space-separated integers.
Output
The maximum coins.
Constraints
- 1 ≤ n ≤ 300
- 0 ≤ a[i] ≤ 100
Think about the LAST balloon k burst inside an open interval (i, j): its neighbours are then i and j. best(i, j) = max over k of best(i, k) + best(k, j) + v[i]·v[k]·v[j], with 1s padded at both ends.
Example 1
Input
4 3 1 5 8
Output
167
Example 2
Input
2 1 5
Output
10
Hints
- Choosing the first balloon to burst makes the subproblems depend on each other. Instead choose the LAST balloon to burst in a range.
- Pad the array with 1 at both ends. If k is the last balloon burst strictly between i and j, it earns v[i]·v[k]·v[j], and the two sides (i, k) and (k, j) are independent.
Approach
dp[i][j] = maximum coins from bursting every balloon strictly between i and j (padded indices). For increasing gap lengths, dp[i][j] = max over k in (i, j) of dp[i][k] + dp[k][j] + v[i]·v[k]·v[j]: when k goes last, its neighbours are exactly the boundaries i and j. The answer is dp[0][n+1].
Complexity: O(n³) time · O(n²) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> v(n + 2, 1);
for (int i = 1; i <= n; i++) cin >> v[i];
int N = n + 2;
vector<vector<long long>> dp(N, vector<long long>(N, 0));
for (int len = 2; len < N; len++)
for (int i = 0; i + len < N; i++) {
int j = i + len;
for (int k = i + 1; k < j; k++) dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + v[i] * v[k] * v[j]);
}
cout << dp[0][N - 1] << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
v = [1] + data[1 : 1 + data[0]] + [1]
N = len(v)
dp = [[0] * N for _ in range(N)]
for length in range(2, N):
for i in range(N - length):
j = i + length
vij = v[i] * v[j]
row_i = dp[i]
best = 0
for k in range(i + 1, j):
cand = row_i[k] + dp[k][j] + vij * v[k]
if cand > best:
best = cand
row_i[j] = best
print(dp[0][N - 1])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] v = new long[n + 2];
v[0] = v[n + 1] = 1;
for (int i = 1; i <= n; i++) v[i] = sc.nextLong();
int N = n + 2;
long[][] dp = new long[N][N];
for (int len = 2; len < N; len++)
for (int i = 0; i + len < N; i++) {
int j = i + len;
for (int k = i + 1; k < j; k++) dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + v[i] * v[k] * v[j]);
}
System.out.println(dp[0][N - 1]);
}
}