Problem
You have n balloons each with a number. Bursting balloon i gives nums[i-1] * nums[i] * nums[i+1] coins (treat boundary as 1). Maximize total coins.
Example
Input: [3,1,5,8]
Output: 167Solution
DP on intervals. dp[i][j] = max coins from bursting all balloons strictly between i and j. Pad nums with 1s on both sides.
def max_coins(nums):
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] * n for _ in range(n)]
for length in range(2, n):
for left in range(n - length):
right = left + length
for k in range(left + 1, right):
dp[left][right] = max(dp[left][right], dp[left][k] + dp[k][right] + nums[left] * nums[k] * nums[right])
return dp[0][n-1]function maxCoins(nums) {
nums = [1, ...nums, 1];
const n = nums.length;
const dp = Array.from({length: n}, () => new Array(n).fill(0));
for (let length = 2; length < n; length++) {
for (let left = 0; left + length < n; left++) {
const right = left + length;
for (let k = left + 1; k < right; k++) {
dp[left][right] = Math.max(dp[left][right], dp[left][k] + dp[k][right] + nums[left] * nums[k] * nums[right]);
}
}
}
return dp[0][n-1];
}int maxCoins(vector<int>& nums) {
nums.insert(nums.begin(), 1);
nums.push_back(1);
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int length = 2; length < n; length++) {
for (int left = 0; left + length < n; left++) {
int right = left + length;
for (int k = left + 1; k < right; k++) {
dp[left][right] = max(dp[left][right], dp[left][k] + dp[k][right] + nums[left] * nums[k] * nums[right]);
}
}
}
return dp[0][n-1];
}public int maxCoins(int[] nums) {
int n = nums.length + 2;
int[] arr = new int[n];
arr[0] = 1; arr[n-1] = 1;
System.arraycopy(nums, 0, arr, 1, nums.length);
int[][] dp = new int[n][n];
for (int length = 2; length < n; length++) {
for (int left = 0; left + length < n; left++) {
int right = left + length;
for (int k = left + 1; k < right; k++) {
dp[left][right] = Math.max(dp[left][right], dp[left][k] + dp[k][right] + arr[left] * arr[k] * arr[right]);
}
}
}
return dp[0][n-1];
}Complexity
- Time: O(n³)
- Space: O(n²)
Explanation
Trick: think backwards. Pick which balloon to burst LAST in each interval. Its neighbors are then the boundary balloons (untouched in this interval).
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?