1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> f(n + 2, vector<int>(n + 2));
        vector<int> val(n + 2);
        val[0] = 1, val[n + 1] = 1;
        for (int i = 1; i <= n; i ++) {
            val[i] = nums[i - 1];
        }
        for (int i = n - 1; i >= 0; i --) {
            for (int j = i + 2; j <= n + 1; j ++) {
                for (int k = i + 1; k < j; k ++) {
                    int sum = val[i] * val[k] * val[j];
                    sum += f[i][k] + f[k][j];
                    f[i][j] = max(f[i][j], sum);
                }
            }
        }

        return f[0][n + 1];
    }
};