image.png

解法

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        // val在左右两侧插入虚拟节点，用来处理边界情况
        int[] val = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        val[0] = val[n + 1] = 1;
        // i和j之间放入气球，能获得的最大值
        int[][] dp = new int[n + 2][n + 2];
        // 开区间，所以i可以取到0,j取到n+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[k] * val[i] * val[j];
                    dp[i][j] = Math.max(dp[i][j], sum + dp[i][k] + dp[k][j]);
                }
            }
        }
        return dp[0][n + 1];                   
    }
}