思路

区间dp

过程

代码

class Solution 
{
    int a[110], f[110][110];
public:
    int getCoins(vector<int>& coins) 
    {
        int n = coins.size();
        a[0] = a[n + 1] = 1;
        for(int i = 1;i <= n;i ++) a[i] = coins[i - 1];
        for(int i = n;i >= 1;i --)
            for(int j = i;j <= n;j ++)
                for(int k = i;k <= j;k ++)
                    f[i][j] = max(f[i][j], f[i][k - 1] + f[k + 1][j] + a[i - 1] * a[k] * a[j + 1]);
        return f[1][n];
    }
};