想了一晚上，自己写出来了，好开心。
关键是要留一行和一列的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];
}
}
