Burst Balloons Problem


Description

LeetCode Problem 312.

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the i^th balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Example 1:

1
2
3
4
5
Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

Example 2:

1
2
Input: nums = [1,5]
Output: 10

Constraints:

  • n == nums.length
  • 1 <= n <= 500
  • 0 <= nums[i] <= 100


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
        for (int len = 1; len <= n; ++len)
            for (int left = 1; left <= n - len + 1; ++left) {
                int right = left + len - 1;
                for (int k = left; k <= right; ++k)
                    dp[left][right] = max(dp[left][right], nums[left-1]*nums[k]*nums[right+1] + dp[left][k-1] + dp[k+1][right]);
            }
        return dp[1][n];
    }
};




Related Posts

Count Numbers With Unique Digits Problem

LeetCode 357. Given an integer n, return the count of...

Combination Sum IV Problem

LeetCode 377. Given an array of distinct integers nums and...

Coin Change Problem

LeetCode 322. You are given an integer array coins representing...

Burst Balloons Problem

LeetCode 312. You are given n balloons, indexed from 0...

Best Time To Buy And Sell Stock With Cooldown Problem

LeetCode 309. You are given an array prices where prices[i]...

Maximum Product Subarray Problem

LeetCode 152. Given an integer array nums, find a contiguous...