LeetCode 312 Burst Balloons

LeetCode 312 Burst Balloons

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:
(1) You may imagine nums[-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]

Return 167

    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

题目大意：

给定n个气球，下标为0到n-1。每个气球上都标有一个数字，用数组nums表示。你被要求扎破所有气球。扎破第i个气球可以获得nums[left] × nums[i] × nums[right]枚硬币。这里left和right是与i相邻的下标。扎破气球以后，left和right就变成相邻的了。
寻找最优策略下可以获得的硬币数。

注意：
(1) 你可以假设nums[-1] = nums[n] = 1. 它们并非真实的因此不能扎破。
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

解题思路：

此题遍历所有可能性，所以考虑用DP
因为一个参数不足以描述问题，因为并不能固定nums左端或右端，所以考虑二元DP，左右边界为参数。DP流程一：定义函数f(i,j)为nums[i..j]之间的最大硬币数。
下一步写递归式，由于这是二元DP，参考Floyd和矩阵链乘法算法，一遍要定义一个k，二分法得到两个子问题的解f(i,k)和f(k,j)，求解它们的关系是难点。先写几个例子培养下思路：
2,3,4
f([2,4])=2×3×4同时消去了3变成[2,4],再写一个
2,3,4,5,6,7,8
k=5, 数组变成[2,5,8]所以我们定义中忽略了一个重要事实，修改为f(i,j)为nums[i..j]之间的最大硬币数及其它们之间的元素已经消去。
这样的话，关系就很明朗了，只要消去5就可以得到f([2,8])，k的定义要可以清晰了：最后一个消去的元素。
f(i,j)=max{f(i,m)+ nums[i]×nums[m]×nums[j] +f(m,j)}, i<m<j，m为整数
我们还要试试nums为单元素和双元素情况下是否适用。比如单元素5，根据题目意思首先前后补1
1,5,1 -> f(1,5)+1×5×1+f(5,1)=5这是正确的因为f(x,y)默认为0.
1,5,3,1, k=5, f(1,5)+1×5×1+f(5,1)=0+5+(5×3×1)=20 | k=3, f(1,3)+1×3×1+f(3,1)=(1×5×3)+3+0=18.所以也是正确，且f(x,y)默认为0没问题。
遍历顺序。一开始我用i,j,m三重循环，但结果不对。主要因为这个计算过程与演算过程不一致，我们刚才的演算过程是先计算所有i和j之间的值。例如，
1, 5, 3, 1
i        j
i            j
    i        j

在第二次循环的时候f(i,j)已经计算出来很显然是不对的。

注意事项：

二元DP([i,j],k的递归式)+二分法。二元DP中k的引入参考Floyd按步长计算。nums[i] * nums[m] * nums[j]而不是nums[m-1] * nums[m] * nums[m+1]
原数组前后补1，这样巧妙地让递归式适用于一个元素的情况，避免特别处理。因此步长可以k=2开始，i<m<j不取等号。dp数组以新数组为边界
遍历顺序也类似于Floyd，先k(步长且至少为2)，再遍历矩阵i和j。特别注意i<n-k而不是i<n

Python代码：

def maxCoins(self, nums: List[int]) -> int:
	ary = list(nums)
	ary.insert(0, 1)
	ary.append(1)
	N = len(ary)
	dp = [[0 for _ in range(N)] for _ in range(N)]
	for k in range(2, N):
		for i in range(0, N - k):
			j = i + k
			for m in range(i + 1, j):
				dp[i][j] = max(dp[i][j], dp[i][m] + ary[i] * ary[m] * ary[j] + dp[m][j])
	return dp[0][N - 1]

Java代码：

public int maxCoins(int[] nums) {
	int n = nums.length+2;
	int[] coins = new int[n];
	
	for(int i=0;i<nums.length;i++)
		coins[i+1]=nums[i];
	coins[0] = coins[n-1] = 1;
	
	int[][] dp = new int[n][n];
	for(int k=2;k<n;k++)
		for(int i=0;i<n - k;i++){
			int j = i+k;
			for(int m=i+1;m<j;m++)
				dp[i][j] = Math.max(dp[i][j], dp[i][m]+coins[i]*coins[m]*coins[j] + dp[m][j]);
				
		}
	return dp[0][n-1];
}

算法分析：

三重循环，时间复杂度为O(n³)，空间复杂度O(n²)。