Burst Ballons

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. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find themaximumcoins you can collect by bursting the balloons wisely.

Example

Example 1:

Input：[4, 1, 5, 10]
Output：270
Explanation：
nums = [4, 1, 5, 10] burst 1, get coins 4 * 1 * 5 = 20
nums = [4, 5, 10]   burst 5, get coins 4 * 5 * 10 = 200 
nums = [4, 10]    burst 4, get coins 1 * 4 * 10 = 40
nums = [10]    burst 10, get coins 1 * 10 * 1 = 10
Total coins 20 + 200 + 40 + 10 = 270

Example 2:

Input：[3,1,5]
Output：35
Explanation：
nums = [3, 1, 5] burst 1, get coins 3 * 1 * 5 = 15
nums = [3, 5] burst 3, get coins 1 * 3 * 5 = 15
nums = [5] burst 5, get coins 1 * 5 * 1 = 5
Total coins 15 + 15 + 5  = 35

• You may imaginenums[-1] = nums[n] = 1. They are not real therefore you can not burst them.

• 0 ≤n≤ 500, 0 ≤nums[i]≤ 100

Note

死胡同：容易想到的一个思路从小往大，枚举第一次在哪吹爆气球？

记忆化搜索的思路，从大到小，先考虑最后一个气球被吹爆之后的获益

将原数组两端加上1 [4,3,5] => [1,4,3,5,1]，数组长度 n 从 3 变为 5

• State: dp[i][j] 表示把第i+1到第j-1个气球打爆，剩下i,j的最大收益

• Function: 对于所有k属于{i + 1,j - 1}, 表示第k号气球最后打爆。

• score = arr[i] * arr[k] * arr[j]

• dp[i][j] = max(dp[i][k]+dp[k][j]+score)

• Intialization: dp[i][i] = 0

• Answer: dp[0][n-1]

区间dp：在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。dp[i][j] 代表 burst i+1 ~ j-1 这段时间的所有气球之后，只剩下 i,j 的最大收益。将原来的数组前面和后面增加两个1，最后结果就是 dp[0][n - 1]（burst 掉所有气球只剩两个1）

i，i+1以及i+2相邻的3个构成最小的区间，然后k和j移动不断扩大更新区间，利用之前小区间的最优解更新大区间的最优解

Code

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

        nums = init(nums);
        int[][] dp = new int[nums.length][nums.length];

        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = i + 2; j < nums.length; j++) {
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] +  dp[k][j] + nums[i] * nums[k] * nums[j]);    
                    //状态转移利用小区间最优解更新大区间
                }
            }
        }

        return dp[0][nums.length - 1];
    }

    public int[] init(int[] nums){                    
        //初始化数组，头部和尾部插入1
        int[] temp = new int[nums.length + 2];
        temp[0] = 1;
        for(int i = 1; i < temp.length - 1; i++){
            temp[i] = nums[i - 1];
        }
        temp[temp.length - 1] = 1;
        return temp;
    }
}

class Solution:
    """
    @param nums: A list of integer
    @return: An integer, maximum coins
    """
    def maxCoins(self, nums):
        if not nums:
            return 0

        # [4,1,5] => [1,4,1,5,1]
        nums = [1, *nums, 1]
        return self.memo_search(nums, 0, len(nums) - 1, {})

    def memo_search(self, nums, i, j, memo):
        if i == j:
            return 0 

        if (i, j) in memo:
            return memo[(i, j)]

        best = 0
        for k in range(i + 1, j):
            left = self.memo_search(nums, i, k, memo)
            right = self.memo_search(nums, k, j, memo)
            best = max(best, left + right + nums[i] * nums[k] * nums[j])

        memo[(i, j)] = best
        return best