戳气球
闫氏DP分析法
class Solution {
public:
int f[510][510];
int maxCoins(vector<int>& nums) {
int n=nums.size();
nums.insert(nums.begin(),1); //防止i-1<0 越界
nums.push_back(1); //防止j+1>n 越界
for(int len=0;len<n;len++){
for(int i=1;i<=n-len;i++){
int j=i+len;
for(int k=i;k<=j;k++){
f[i][j]=max(f[i][j],f[i][k-1]+f[k+1][j]+nums[k]*nums[i-1]*nums[j+1]);
}
}
}
return f[1][n];
}
};