LeetCode312. 戳气球

方法：动态规划，定义二维数组 coins，coinsa 表示把第 a 个气球和第 b 个气球之间（不包括 a 和 b）的气球戳烂，最大能得到的分值

public class Solution {
    public int maxCoins(int[] nums) {
        int[] dpnums = new int[nums.length + 2];
        dpnums[0] = 1;
        dpnums[dpnums.length - 1] = 1;
        for(int i = 0, j = 1; i < nums.length; i++, j++) 
            dpnums[j] = nums[i];
        int[][] coins = new int[dpnums.length][dpnums.length];
        for(int i=2; i<dpnums.length; i++) {
            for(int j=0; j+i<dpnums.length; j++) {
                for(int k=j+1; k<j+i; k++) {
                    coins[j][j+i] = Math.max(coins[j][j+i], coins[j][k] + coins[k][j+i] +
                        dpnums[j] * dpnums[k] * dpnums[j+i]);
                }
            }
        }
        return coins[0][dpnums.length-1];
    }
}