有点意思的题目 可以看做合并
dp下标选取为L,R的闭区间
然后遍历合并点得到dp递推式
题目链接
class Solution {
public:
int d[maxn][maxn];
int maxCoins(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
memset(d,0,sizeof(d));
//d[i][j] = for k in (i,j) max(d[i][k - 1] + d[k + 1][j] + nums[k]*nums[i - 1]*nums[j + 1])
for(int i = 0; i < n; i ++){
int L = 1, R = 1;
if(i > 0) L = nums[i - 1];
if(i < n - 1) R = nums[i + 1];
d[i][i] = L * nums[i] * R;
}
for(int len = 2; len <= n; len ++){
for(int i = 0; i < n; i ++){
int j = i + len - 1;
if(j > n - 1) break;
for(int k = i; k <= j; k ++){
int sum_L = 0, sum_R = 0;
if(i <= k - 1) sum_L = d[i][k - 1];
if(k + 1 <= j) sum_R = d[k + 1][j];
int L = 1, R = 1;
if(i > 0) L = nums[i - 1];
if(j < n - 1) R = nums[j + 1];
d[i][j] = max(d[i][j], sum_L + sum_R + L * nums[k] * R);
}
}
}
/*
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++)
printf("%d ",d[i][j]);
putchar('\n');
}
printf("%d\n",d[0][n - 1]);
*/
return d[0][n - 1];
}
};