【Lintcode】168. Burst Balloons

题目地址：

https://www.lintcode.com/problem/burst-balloons/description

给定一个数组 A A A，每个数代表一个气球的分值，允许一次戳破一个气球，每次戳破气球的时候，得到的分数是，该气球的分值，与其左边最近的未戳破的气球分值乘积，再与其右边最近的未戳破的气球的分值乘积。如果左边没有或者右边没有未戳破的气球，就想象有一个分值为 1 1 1的气球即可。问戳破全部气球可以得到的最大分值是多少。

思路是记忆化搜索。设 f [ i ] [ j ] f[i][j] f[i][j]是戳破 A [ i : j ] A[i:j] A[i:j]所能得到的最大分值，则可以按照最后戳破的是哪个气球进行分类，如果最后戳破的是 A [ k ] A[k] A[k]，那么最高得分应该是 f [ i ] [ k − 1 ] + f [ k + 1 ] [ j ] + A [ k ] A [ i − 1 ] A [ j + 1 ] f[i][k-1]+f[k+1][j]+A[k]A[i-1]A[j+1] f[i][k−1]+f[k+1][j]+A[k]A[i−1]A[j+1]。枚举 k k k选一个最大的即可。代码如下：

public class Solution {
    /**
     * @param nums: A list of integer
     * @return: An integer, maximum coins
     */
    public int maxCoins(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int len = nums.length;
        int[][] dp = new int[len + 1][len + 1];
        
        return dfs(0, len - 1, dp, nums);
    }
    
    private int dfs(int l, int r, int[][] dp, int[] nums) {
    	// 如果有记忆则调取记忆
        if (dp[l][r] != 0) {
            return dp[l][r];
        }
        // 枚举最后戳破的是哪个气球
        for (int i = l; i <= r; i++) {
            int left = 0, right = 0;
            if (i - 1 >= l) {
                left = dfs(l, i - 1, dp, nums);
            }
            if (i + 1 <= r) {
                right = dfs(i + 1, r, dp, nums);
            }
            
            dp[l][r] = Math.max(dp[l][r], left + right + nums[i] * (l - 1 >= 0 ? nums[l - 1] : 1) * (r + 1 < nums.length ? nums[r + 1] : 1));
        }
        
        return dp[l][r];
    }
}
           

时间复杂度 O ( n 3 ) O(n^3) O(n3)，空间 O ( n 2 ) O(n^2) O(n2)。