312 Burst Balloons

312. Burst Balloons

1. Question

Givennballoons, indexed from0ton-1. Each balloon is painted with a number on it represented by arraynums. You are asked to burst all the balloons. If the you burst ballooniyou will getnums[left] * nums[i] * nums[right]coins. Hereleftandrightare adjacent indices ofi. After the burst, theleftandrightthen becomes adjacent.

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

Note: (1) You may imaginenums[-1] = nums[n] = 1. They are not real therefore you can not burst them. (2) 0 ≤n≤ 500, 0 ≤nums[i]≤ 100

Example:

Given[3, 1, 5, 8]

Return167

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

2. Implementation

(1) DP

思路: 这题其实和Matrix Chain Multiplication一模一样，只是换方法表述而已，还是区间DP的思想。dp[i][j]表示在区间[i, j]我们可以获得的最大分数。根据题意，我们知道每爆一个气球nums[i]，我们可以获得nums[left] * nums[i] * nums[right]的分数，那么在[i, j]区间里，我们可以找到一个点k使得 nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]最大，于是状态转移方程为

dp[i][j] = Math.max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + nums[i - 1] * nums[k] * nums[j + 1]

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

        int n = nums.length;
         // Add 2 because we wanna include the boundary nums[-1] and nums[n]
        int[] coins = new int[n + 2];
        coins[0] = 1;
        coins[n + 1] = 1;

        for (int i = 1; i <= n; i++) {
            coins[i] = nums[i - 1];
        }

        // 我们要找的答案在dp[1][n]
        // dp[i][j] means the max coins we can collect in the coin(i..j)
        int[][] dp = new int[n + 2][n + 2];

        for (int len = 1; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int end = start + len - 1;

                for (int mid = start; mid <= end; mid++) {
                    dp[start][end] = Math.max(dp[start][end], dp[start][mid - 1] + dp[mid + 1][end] + coins[start - 1] * coins[mid] * coins[end + 1]);
                }
            }
        }
        return dp[1][n];
    }
}

3. Time & Space Complexity

DP: 时间复杂度O(n^3), 空间复杂度O(n^2)