p312

发表于 | 分类于 |

LeetCode 312 Burst Balloons 题解

1.题目：

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 = 315 + 358 + 138 + 181 = 167

题意：

输入一个数组，每个气球都有值，你扎气球，扎破一个获得这个气球和它两边的气球价值乘积
的硬币，求你能够获得的最多硬币。

2.解题思路:

写在前面：这题我想了两天。。最后看别人题解，还没有太看懂，N3复杂度的东西，自己徒手过了一遍流程，才略微有点感觉。
所以如果看不懂我写的题解，一定是我的问题TUT。
首先将以为数组扩展：左边右边都加上1，便于进行乘法计算。
在创建一个二维数组，用来记录和更新d[left][right] 从左端点到右端点的最大值。
现在我们从后往前推理，最后一个进行计算的数，等于他自己乘以这一段最左相邻，和最右相邻，加上左半段的值和右半段的值。（mark,为啥一定是左相邻和右相邻我也不太懂原理，但是反正会取大记录TUT
（mark mark mark 以后来解释TUT
然后一直这样倒退回去。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 

public class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length < 1)
			return 0;
		int len = nums.length;
		int[] a = new int[len + 2];
		a[0] = 1;
		a[len + 1] = 1;

		for (int i = 1; i < len + 1; i++) {
			a[i] = nums[i - 1];
		}
		// int left=0;
		// int right=len+2;
		int[][] d = new int[len + 2][len + 2];
		for (int right = 1; right < len + 1; right++) {//右端点
			for (int left = right; left > 0; left--) {//为每一个右端点找出可能的左端点

				for (int k = 0; k + left <= right; k++) {
					d[left][right] = Math.max(d[left][right], a[left - 1]
							* a[right + 1] * a[k + left]
							+ d[left][k + left - 1] + d[k + left + 1][right]);
					// System.out.println(left + "   " + right + "   "
					// + d[left][right]);
				}
			}
		}
		return d[1][len];
    }
}

4.一些总结：