题目大意：
戳气球
有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。每当你戳破一个气球 i 时，你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:
- 你可以假设
nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。 - 0 ≤
n≤ 500, 0 ≤nums[i]≤ 100
示例:
输入:[3,1,5,8]
输出: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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=312
解题思路：
这是一道DP（动态规划）的题目，看到这种求极值的问题，应该首先想到利用动态规划去思考思路。本题为Hard题目，难点在于如何建立DP数组，以及推导出递推公式。
我们首先建立一个二维数组dp[i][j]，用来表示在区间i到j范围内戳破所有气球能得到的最大分数，通过递推公式逐步求解，最终dp[0][length-1]即为题目答案。
接下来，看下如何写出推导公式。对于，任意一个区间[i, j]，如果我们想戳破一个气球k，k在i和j的范围内(i <= k <= j)，这时我们可以将这个区间变为三个部分：
[i, k - 1], [k], [k + 1, j] // k在i和j中间 [i, k - 1], [k], [] // k等于j [], [k], [k + 1, j] // k等于i [], [k], [] // k == i == j
不论k在i和j中间的什么位置，我们都可以将这一段分为3个子问题，我们分别称这三部分为：左，中，右。中间部分是我们这一步想要戳破的气球，它的长度永远只会是1（因为我们不能同时戳两个球）。左右两部分则分别是 dp[i][j] 的子问题 dp[i][k-1] 和 dp[k+1][j] 的解。根据题目，中间部分的值 dp[k][k] 则应该是nums[k] * nums[k’ left] * nums[k’ right]。那么k的左和右是哪两个位置的值呢？显然 k-1 和 k+1 并不是正确答案，原因很简单，不论k-1还是k+1，他们都存在于左右两个子问题中，我们定义的dp数组是代表该区间内所有气球都已经戳破的条件下，既然已经被戳破，那么我们就不能再利用这个值了，因此，k坐标的左右相邻的气球坐标应该是当前i和j范围的相邻位置，即i-1和j+1。至此，我们可以清晰的写出推导公式：
dp[i][j] = Max(dp[i][k-1] + nums[k] * nums[i-1] * nums[j+1] + dp[k+1][j]); // i <= k <= j
简单的再总结一下这个公式，当前区间i和j范围内，我们取一个坐标k，对于每个k，我们都可以计算出一个当我们戳破下标为k的气球时能得到的分数，遍历完所有k的情况，最大分数即是当前范围内的最优解。
推导公式已经清楚。接下来我们考虑下怎么利用这个公式写代码。我们注意到，如果想计算出一个区间的最优解，我们需要先知道这个区间内子问题的解，因此在做dp运算时，我们应该从最短的区间（长度为1的区间）开始，这也是dp的初始条件，对于长度为1的最小区间，戳破每一个气球所能得到的最大分数即是：
dp[i][i] = nums[i] * nums[i-1] * nums[i+1];
这个计算公式，其实已经包含在上面讲到的递推公式中了，当i和j相同时，k也等于i和j，这样，dp[i][k-1]和dp[k+1][j]超出了当前范围，计算结果为0，因此就只剩下中间k的这一个部分了。
当我们得到了所有最小范围的解后，我们可以将范围扩大到2，再扩大到3，直到扩大为题目给出数组的整体范围，此时dp结束。
我们来看下实现代码。
public int maxCoins(int[] nums) {
int length = nums.length; // 数组长度
// 数组长度为0时，还计算个毛线，直接返回0。
if (length == 0) {
return 0;
}
// 定义2维dp数组，表示该区间内戳破所有气球能获得的最大分数。
int dp[][] = new int[length][length];
// 第一层循环是在变换区间的长度范围，变量i表示从0到数组长度-1
// 注意，这里长度范围为0代表区间的左右下标相同。即right-left=0
for (int i = 0; i < length; i++) {
// 第二层循环是在改变区间的起始位置，从0到数组末尾。
// 不过要考虑到区间的长度，起始位置+长度如果越界则不再考虑范围之内。
// 此时for循环的第二个语句应该写为j + i < length
for (int j = 0; j + i < length; j++) {
// 根据区间长度i和起始位置j，计算出区间的左右下标。
int leftIndex = j, rightIndex = j + i;
// 在当前区间内遍历戳破所有气球时能得到的分数。
// 变量k表示在当前区间内戳破哪个气球
for (int k = leftIndex; k <= rightIndex; k++) {
// 以k分割区间，从dp中取出区间左部分的值
int left = k == leftIndex ? 0 : dp[leftIndex][k - 1];
// 以k分割区间，从dp中取出区间右部分的值
int right = k == rightIndex ? 0 : dp[k + 1][rightIndex];
// 计算出戳破气球k能得到的分数
int current = nums[k] * (leftIndex > 0 ? nums[leftIndex - 1] : 1)
* (rightIndex + 1 < length ? nums[rightIndex + 1] : 1);
// 计算出左中右三部分的和，如果大于之前计算的结果，更新dp
dp[leftIndex][rightIndex] = Math.max(dp[leftIndex][rightIndex], left + right + current);
}
}
}
// 返回最终答案
return dp[0][length - 1];
} 本解法平均用时6ms
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-312-burst-balloons-解题思路分析/