有点意思的题目 可以看做合并
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];
    }
};