[leetcode] 312. Burst Balloons

Description

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:

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      

分析

題目的意思是：

給你一組氣球，球上面有數字，如果你紮破其中的一個球，你會得到這個氣球和左右相鄰氣球相乘值的硬币。現在要求你能得到的最大的硬币數

• 這道題目是leetcode上面的hard難度的題目，我應該做不出來，是以就沒為難自己了，直接上别人的代碼.

  題目中說明了邊界情況，當氣球周圍沒有氣球的時候，旁邊的數字按1算，這樣我們可以在原數組兩邊各填充一個1，這樣友善于計算。

  這道題的最難點就是找遞歸式，如下所示：

代碼

class Solution {
public:
    int maxCoins(vector<int>& nums) {
       vector<int> temp(nums.size()+2,0);
        int n=1;
        for(auto num:nums){
            if(num>0){
                temp[n]=num;
                n++;
            }
        }
        temp[0]=temp[n]=1;
        n++;
        int dp[n][n]={};
        for(int k=2;k<n;k++){
            for(int left=0;left<n-k;left++){
                int right=left+k;
                for(int i=left+1;i<right;i++){
                    dp[left][right]=max(dp[left][right],temp[left]*temp[i]*temp[right]+dp[left][i]+dp[i][right]);
                }
            }
        }
        return dp[0][n-1];
    }
};      

參考文獻