leetcode312 戳气球

思路：

逆向思维，一个一个移除气球不好处理，改为一个一个增加气球，就可以使用区间dp计算了。

实现：

 1 class Solution {  2 public:  3     int maxCoins(vector<int>& nums) {  4         int n=nums.size();  5         vector<int>a(n+2,1);  6         for(int i=0;i<n;i++){  7             a[i+1]=nums[i];  8         }  9         vector<vector<int>>dp(n+2,vector<int>(n+2,0)); 10         for(int i=n+1;i>=0;i--){ 11             if(i+2<=n+1)dp[i][i+2]=a[i]*a[i+1]*a[i+2]; 12             for(int j=i+3;j<=n+1;j++){ 13                 for(int k=i+1;k<j;k++){ 14                     dp[i][j]=max(dp[i][j],dp[i][k]+a[k]*a[i]*a[j]+dp[k][j]); 15                 } 16             } 17         } 18         return dp[0][n+1]; 19     } 20 };