LeetCode312. 戳气球

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

代码语言：javascript复制

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];
    }
}

动态规划 数组

0 人点赞