参考文献
ref{:target=”_blank”}
区间dp,在首尾各添加一个1,方便计算
C++ 代码
class Solution {
public:
// f[i, j] 表示 (i, j) 区间内的收益
int maxCoins(vector<int>& nums) {
int n = nums.size();
vector<int> nums_(n+2, 1);
for(int i=0; i<n; ++i)nums_[i+1] = nums[i];
vector<vector<int>> f(n+2, vector<int>(n+2, 0));
for(int len = 3; len <= n+2; ++len){
for(int i=0; i + len -1 <= n+1; ++i){
int j = i+len-1;
// k 表示(i,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_[k]*nums_[j]);
// cout << f[i][j] << "," << i << "," << j << endl;
}
}
}
return f[0][n+1];
}
};