312.戳气球

• 将戳气球转换到添加气球，记忆搜索
• slove(i,j)：在开区间(i,j)全部填满气球得到的最多硬币数，两端val[i]、val[j]

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> val;

    int slove(int left,int right){
        if(left>=right-1) return 0;
        if(ans[left][right]!=-1) return ans[left][right];

        
        for(int i=left+1;i<right;i++){
            int sum=val[left]*val[i]*val[right];
            sum+=slove(left,i);
            sum+=slove(i,right);
            ans[left][right]=max(ans[left][right],sum);
        }
        return ans[left][right];
    }

    int maxCoins(vector<int>& nums) {
        int n=nums.size();
        val.resize(n+2);
        for(int i=1;i<=n;i++){
            val[i]=nums[i-1];
        }
        val[0]=val[n+1]=1;

        ans.resize(n+2,vector<int>(n+2,-1));
        return slove(0,n+1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31