Burst Balloons

来自https://leetcode.com/problems/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

思路1

很快就能想到递归思路。第一步选择0到n之间的一个，把列表分成左右两段子序列，子序列继续运算。

public int maxCoins(int[] nums)
{
	int maxCoins = 0;

	for (int i = 0; i < nums.length; i++)
	{
		if (nums[i] < 0)
			continue;
		int coin = nums[i];
		nums[i] = -1;

		int burstCoin = getLeftCoin(nums, i) * coin * getRightCoin(nums, i);

		burstCoin += maxCoins(nums);
		if (burstCoin > maxCoins)
			maxCoins = burstCoin;

		nums[i] = coin;
	}

	return maxCoins;
}

private int getLeftCoin(int[] nums, int index)
{
	for (int i = index - 1; i >= 0; i--)
	{
		if (nums[i] >= 0)
			return nums[i];
	}

	return 1;
}

private int getRightCoin(int[] nums, int index)
{
	for (int i = index + 1; i < nums.length; i++)
	{
		if (nums[i] >= 0)
			return nums[i];
	}

	return 1;
}

空间上，没有额外辅助结构，只是递归需要堆栈，所以是O(n)。

时间上，第一步有n个选择。假设第一步选择最左边一个，则只产生一个子序列，有n-1个选择。假设第二步也选择最左边一个，则第三步有n-2个选择……所以时间复杂度是O(n!)。

这个解法没有利用问题的任何性质，必然是慢的。如果发现性质，可能有更快的解法。

一般的解题思路：

1. 先手工计算，体会问题
2. 如果超出边界可以想象成有虚拟的成员，不如把头尾的虚拟成员包括进来，想象成边界缩小了。
3. 寻找性质，不利用性质的算法一般都是慢的。

以题目中的[3,1,5,8]为例，1表示被戳破的气球。难点：气球被戳破后，不能缩小数组长度。3,1,5,8不能变成3,5,8，必须保留原来1的位置！

可以找到性质：

但这个性质太具体了，我们需要更一般化的性质。按照一般解题思路(2)，扩展序列，把头尾的1包括进来。并且，最后一颗球的可能位置是0到n-1。把这个范围称为可能范围。即第n步后，我们戳破了第n个气球，所有气球都没了。如果有个人现在才过来看我们戳气球，他只知道我们戳的最后一个气球，一定落在起点为0长度为4的可能范围中。

从最后一步归纳到第t步：在第t步之后，现场还剩余一些气球，则在第t步被戳破的气球，一定在剩余的气球所划分的某个区间内。例如第3步之后，现场的气球设置为 , ,5,，请问我第3步戳了哪个气球？

答：有两种可能。第3步戳的气球，要么在起点为0长度为2的第一个可能范围里，要么在起点为3长度为1的第二个可能范围里。
 , ,5,

可能范围可以用起点[latex]s[/latex]和长度[latex]l[/latex]来唯一标识。性质1.1可一般化为

但是[latex]s-1[/latex]和[latex]s+l+1[/latex]位置的气球会不会已经被戳破了呢？不会的。因为可能范围是由还存在的气球所界定的，可能范围两边一定有气球！

那么如何获得最多的金币呢？

递推公式昭然若揭！

public int maxCoins2(int[] nums)
{

	return maxCoins(nums, 0, nums.length);
}

public int maxCoins(int[] nums, int start, int length)
{
	int max = 0;
	for (int i = start; i < start + length; i++)
	{
		int c = (start - 1 < 0 ? 1 : nums[start - 1]) * nums[i] * (start + length >= nums.length ? 1 : nums[start + length]);
		c += maxCoins(nums, start, i - start) + maxCoins(nums, i + 1, length - (i - start) - 1);

		if (c > max)
			max = c;
	}

	return max;

}

但这个算法有个问题，就是会重复解决问题。注意到较长的可能范围依赖较短的可能范围，说明应该用动态规划，递增可能范围的长度。现在给出最终方案。

public int maxCoins(int[] nums)
{
	int[][] store = new int[nums.length + 1][nums.length + 1];

	for (int length = 1; length <= nums.length; length++)
	{
		for (int sequenceStart = 0; sequenceStart + length <= nums.length; sequenceStart++)
		{
			for (int index = sequenceStart; index < sequenceStart + length; index++)
			{
				int leftCoin = sequenceStart - 1 < 0 ? 1 : nums[sequenceStart - 1];
				int rightCoin = sequenceStart + length >= nums.length ? 1 : nums[sequenceStart + length];// index<nums.length-1

				int totalCoin = leftCoin * nums[index] * rightCoin + store[index - sequenceStart][sequenceStart]
						+ store[length - (index - sequenceStart) - 1][index + 1];
				if (store[length][sequenceStart] < totalCoin)
					store[length][sequenceStart] = totalCoin;
			}
		}
	}

	return store[nums.length][0];
}

思路2

反转过程，戳气球改为种气球：场地上有n个空位，可假设-1位和n位已有气球，价值为1；你有n颗气球，每在这n个空位里放一颗气球，获得金币。

用同一个例子，目标状态是3,1,5,8。

写出的代码是一样的。

总结

因为自己实在想不到，只好记住：

一般的解题思路：

1. 先手工计算，体会问题
2. 如果超出边界可以想象成有虚拟的成员，则可把头尾的虚拟成员包括进来，想象成边界缩小了。
3. 寻找性质，不利用性质的算法一般都是慢的。
4. 尝试反转过程，把最后一步改为第一步，倒着来算。