【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)。