1、前言

2、思路

二维数组，从左往右遍历

3、代码

   public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] coins = new int[n + 2];
        coins[0] = 1;
        coins[n + 1] = 1;
        for(int i = 1; i <= n; i++){
            coins[i] = nums[i - 1];
        }

        int[][] dp = new int[n + 2][n + 2];
        for(int i = n; i >= 0; i--){
            for(int j = i + 1; j <= n + 1; j++){
                for(int k = i + 1; k < j; k++){
                    dp[i][j] = Math.max(
                            dp[i][j],
                            dp[i][k] + dp[k][j] + coins[i] * coins[j] * coins[k]
                    );
                }
            }
        }
        return dp[0][n + 1];
    }