Burst Ballons

一、题目

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: (1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them. (2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

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

二、思路分析

这个题目一开始我是很没有头绪的，因为不知道要从哪里开始。但是我看到了另外一个博客的一句话，“最后一个数将数组分为了两部分”我就明白了这道题为什么会有分而治之的标签，这是一道用到分而治之思想的动态规划题。随便拿一个数组来说，假如它的第i个数字是最后消除的那个数字，那么i的左边跟右边的数字在计算金币值是毫不相关的因此可以看成两个子问题，然后这两个子问题再继续求解。但是若直接用递归的方法，时间消耗很大，于是我想到了用动态规划的方法，将结果保存在dp数组里， dp[k][l]表示 从第k个数字到第l个数字能获得的最大金币值。最后通过三重循环就能让dp[1][n]处的值即为答案。

三、代码

class Solution { public: int maxCoins(vector<int>& nums) { vector<int>temp; int n=nums.size(); int **dp=new int*[n+2]; for(int i=0;i<n+2;i++) dp[i]=new int[n+2]; //开dp二维数组 for(int i=0;i<n+2;i++) for(int j=0;j<n+2;j++) dp[i][j]=0; temp.push_back(1); for(int i=0;i<n;i++){ temp.push_back(nums[i]); } temp.push_back(1); for(int length=1;length<=n;length++){ //三重循环 for(int b=1;b<=n-length+1;b++){ int e=b+length-1; for(int i=b;i<=e;i++){ dp[b][e]=max(dp[b][e],dp[b][i-1]+dp[i+1][e]+temp[i]*temp[b-1]*temp[e+1]); //通过递推得出式子 } } } return dp[1][n]; } };

四、总结

这个题目还是比较难的，我也是受到了一句话的启发才想明白了这个问题，希望以后能增强这方面的能力。