Burst Balloons (H)

题目

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

• You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
• 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Input: [3,1,5,8]
Output: 167 
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

---

题意

打气球游戏。每个气球有对应的分值，打爆一个气球i，能得到的积分为气球i、气球i-1、气球i+1积分的乘积。要求计算能够获得的最大积分。

思路

动态规划问题。dp[left, right]表示打爆从left到right所有气球能得到的最大积分。每一次我们在[left, right]这个区间中选择一个i，代表该区间中最后一个被打爆的气球，那么可以得到递推关系式：

\[dp[left,\ right]=\max_{left \le i \le right}(dp[left,\ i-1]+dp[i+1,\ right]+nums[left-1]*nums[i]*nums[right+1]) \]

---

代码实现

Java

记忆化搜索

class Solution {
    public int maxCoins(int[] nums) {
        int[][] memo = new int[nums.length][nums.length];
        for (int i = 0; i < nums.length; i++) {
            Arrays.fill(memo[i], -1);
        }
        return dfs(nums, 0, nums.length - 1, memo);
    }

    private int dfs(int[] nums, int left, int right, int[][] memo) {
        if (right < left) {
            return 0;
        }
        if (memo[left][right] != -1) {
            return memo[left][right];
        }
        int max = 0;
        for (int i = left; i <= right; i++) {
            int x = dfs(nums, left, i - 1, memo)
                    + dfs(nums, i + 1, right, memo)
                    + nums[i] * (left == 0 ? 1 : nums[left - 1]) * (right == nums.length - 1 ? 1 : nums[right + 1]);
            max = Math.max(max, x);
        }
        memo[left][right] = max;
        return max;
    }
}

动态规划

class Solution {
    public int maxCoins(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int[][] dp = new int[nums.length][nums.length];
        for (int right = 0; right < nums.length; right++) {
            for (int left = right; left >= 0; left--) {
                for (int i = left; i <= right; i++) {
                    int leftMax = i == left ? 0 : dp[left][i - 1];
                    int rightMax = i == right ? 0 : dp[i + 1][right];
                    int last = nums[i] * (left == 0 ? 1 : nums[left - 1]) * (right == nums.length - 1 ? 1 : nums[right + 1]);
                    dp[left][right] = Math.max(dp[left][right], leftMax + rightMax + last);
                }
            }
        }
        return dp[0][nums.length - 1];
    }
}