//解法一：dp 左开右开区间写法
class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n + 2];
        arr[0] = arr[n + 1] = 1;
        for(int i = 1; i <= n; i++)
            arr[i] = nums[i - 1];
        int[][] dp = new int[n + 2][n + 2];
        for(int len = 1; len <= n + 2; len++){
            for(int l = 0; l + len - 1 <= n + 1; l++){
                int r = l + len - 1;
                for(int k = l + 1; k < r ; k++){
                    dp[l][r] = Math.max(dp[l][r], dp[l][k] + dp[k][r] + arr[l] * arr[k] * arr[r]);
                }
            }
        }
        return dp[0][n + 1];
    }
}

//解法二：左闭右闭区间写法
class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n + 2];
        arr[0] = arr[n + 1] = 1;
        for(int i = 1; i <= n; i++)
            arr[i] = nums[i - 1];
        int[][] dp = new int[n + 1][n + 1];
        for(int len = 1; len <= n; len++){
            for(int l = 1; l + len - 1 <= n; l++){
                int r = l + len - 1;
                for(int k = l; k <= r ; k++){
                    int t = (k - 1 >= l ? dp[l][k - 1] : 0) + (k + 1 <= r ? dp[k + 1][r] : 0) + arr[l - 1] * arr[k] * arr[r + 1];
                    dp[l][r] = Math.max(dp[l][r], t);
                }
            }
        }
        return dp[1][n];
    }
}

//解法三：记忆化搜索 左开右开
class Solution {
    int[][] rec;
    int[] val;
    public int maxCoins(int[] nums) {
        int n = nums.length;
        val = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        val[0] = val[n + 1] = 1;
        rec = new int[n + 2][n + 2];
        for (int i = 0; i <= n + 1; i++) {
            Arrays.fill(rec[i], -1);
        }
        return solve(0, n + 1);
    }

    public int solve(int l, int r){
        if(l >= r - 1)
            return 0;
        if(rec[l][r] != -1)
            return rec[l][r];
        for(int i = l + 1; i < r; i++){
            int sum = val[l] * val[i] * val[r];
            sum += solve(l, i) + solve(i, r);
            rec[l][r] = Math.max(rec[l][r], sum);
        }
        return rec[l][r];
    }
}