class Solution {
    // dp[i][j] 代表戳i到j之间内的气球能获得的硬币最大值
    // 递推公式：dp[i][j] = Math.max (dp[i][k] + dp[k][j] + val[i]*val[j]*val[k], dp[i][j])
    // k代表最后一次戳的气球
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n + 2][n + 2];
        int[] val = new int[n + 2];
        val[0] = val[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        for (int len = 1; len <= n; len++) {  // 可以戳的气球数量
            for (int i = 1; i <= n - len + 1; i++) { // 可以戳的起点
                int j = i + len - 1; // 终点
                for (int k = i; k <= j; k++) { // 最后一个戳的气球
                   dp[i][j] = Math.max (dp[i][k-1] + dp[k + 1][j] + val[i-1]*val[j+1]*val[k], dp[i][j]);
                }
            }
        }
        return dp[1][n];
    }    
}