📚312. Burst Balloons

想了一晚上，自己写出来了，好开心。
关键是要留一行和一列的margin。

public class Solution {
    public int maxCoins(int[] nums) {
        // extend the nums array;
        int n = nums.length;
        int coins[] = new int[n+2];
        int m = 1;
        for(int x : nums)
            coins[m++] = x;
        coins[0] = coins[n+1] = 1;
        
        int dp[][] = new int[n+1][n+1];
        for(int k=1; k<=n; k++) {
            for(int left=0; left<=n-k; left++) {
                int right = left + k;
                for(int i=left+1; i<=right; i++) {
                    dp[left][right] = Math.max(dp[left][right], dp[left][i-1]+dp[i][right]+coins[left]*coins[right+1]*coins[i]);
                }
            }
        }
        return dp[0][n];
    }
}