problem:312. 戳气球

思路：根据题目，我们很容易想到可以首尾都插入1作为边界。接下来我们不妨考虑一下最后一步是怎么样的，就拿[1,5]来说，最后一步肯定是只剩下了一个数，再乘以两边的边界值(nums[i],nums[j]),由此我们可以状态定义，f[i][j]表示(i,j)开区间的最大数量硬币，在考虑转移方程，f[i][j] = max(f[i][j],f[i][k]+f[k][j]+nums[i]*nums[j]*nums[k])；入口即为f[0][n-1]，边界f[i][j] = 0,if i>=j

Accode:
记忆化搜索：

class Solution {
public:
    long cache[303][303];
    vector<int> nums;
    long dfs(int i,int j){
        if(i>=j) return 0;
        if(cache[i][j]) return cache[i][j];
        long ans = 0;
        for(int mid = i+1;mid<j;mid++){
            ans = max(ans,dfs(i,mid)+dfs(mid,j)+nums[i]*nums[j]*nums[mid]);
        }
        return cache[i][j] =  ans;
    }
    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        int n  =nums.size();
        this->nums = nums;
        memset(cache,0 ,sizeof cache);
        return dfs(0,n-1);
    }
};

时间复杂度:$o(n^3)$

递推：

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        int n = nums.size();
        long f[n][n];
        memset(f,0,sizeof f);
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                for(int k=i+1;k<j;k++){
                    f[i][j] = max(f[i][j],f[i][k]+f[k][j]+nums[i]*nums[j]*nums[k]);
                }
            }
        }
        return f[0][n-1];
    }
};

时间复杂度：同上