LeetCode 97 每日一题 Day 11.

昨天的题好难，没搞懂，后来把题解cpoy上去了，，，哎我好菜，
今天的也不大会，看了几个题解，才明白大概是怎么回事
先上代码吧，虽然也是参考别人题解的

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

大概思路是：
在序列中，总会有最后一个被扎破的气球，那么这个气球的硬币数就是boo[i]，总的硬币是dp[0][i-1]+boo[i]+boo[i+1][n+1]
可以看到，每一段都有一个最后被扎破的气球，则每一段都可以由其他段动态规划得出
dp[j][j+i]=max(boo[k]*boo[j]*boo[i+j]+dp[j][k]+dp[k][i+j],dp[j][i+j])
boo是存气球数字的，j是开始，j+i是结束，k是最后一个气球的索引值

看起来逻辑还好，但是实现的时候老师有我想不到的地方，一开始我想的是可以用类似贪心法，选最大的一个作为最后一个气球，但实现起来好麻烦。。
就这样吧。还要努力啊