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);}
};