leetcode-312-Burst Balloons

Posted on | In , | |
Words count in article: 597 | Reading time ≈ 3

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

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

Note:

  • You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

1
2
3
4
Input: [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

the visualization help me to understand hope it can help you too.

1···················1

add two 1 at beginning and end of nums, each · represent each number in nums.

len is the subinterval length, it grows from 1 to full length of orignal nums string.

the following illustrations demonstrate how the subinterval shift from left to right. (len = 7 in the illustration)

for each len, when shifted to rightmost, increase len and do the shift again. this way we can evaluate all possible subintervals.

for each subinterval, in the innermost for loop, find which balloon to burst LAST that will give us the most coins for that subinterval. <- IMPORTANT TO UNDERSTAND THIS

dp[left][right] is the maximum coins we can get from left to right. note when left > right, it is 0

for the example [3, 1, 5, 8], the dp matrix is updated like this

1
2
3
4
5
6
0    0    0    0    0    0
0    3    0    0    0    0
0    0    15   0    0    0
0    0    0    40   0    0
0    0    0    0    40   0
0    0    0    0    0    0

then

1
2
3
4
5
6
0    0    0    0    0    0
0    3    30   0    0    0
0    0    15   135  0    0
0    0    0    40   48   0
0    0    0    0    40   0
0    0    0    0    0    0

at last

1
2
3
4
5
6
0    0    0    0    0    0
0    3    30   159  167  0
0    0    15   135  159  0
0    0    0    40   48   0
0    0    0    0    40   0
0    0    0    0    0    0

the code is like most others.

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];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxCoins(int[] nums) {
        int[] A = new int[nums.length+2];
        int n = A.length;
        for(int i=0; i<nums.length; i++)
            A[i+1] = nums[i];
        A[0] = A[n-1] = 1;
        int[][] dp = new int[n][n];
        for(int left = n-3; left >= 0; left--)
        {
            for(int right = left + 2; right < n; right++)
            {
                for(int i=left + 1; i<right; i++)
                    dp[left][right] = Math.max(dp[left][right], dp[left][i] + dp[i][right] + A[left]*A[i]*A[right]);
            }
        }
        return dp[0][n-1];
    }
}
Donate? comment?