## 打破气球所能获得的最大积分 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个气球。每次你可以打破一个，打破第i个，那么你会获得nums[left] * nums[i] * nums[right]个积分。 （nums[-1] = nums[n] = 1）求你可以获得的最大积分数。

① https://segmentfault.com/a/1190000007297715

dp[i][j] = max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j])

( i ≤ k ≤ j )，O(N^2), O(N^2)

class Solution { //15ms
public static int maxCoins(int[] nums) {
int[] tmpnums = new int[nums.length + 2];
System.arraycopy(nums,0,tmpnums,1,nums.length);
tmpnums[0] = 1;
int len = tmpnums.length;
tmpnums[len - 1] = 1;
int[][] dp = new int[len][len];
for (int l = 2;l < len;l ++){
for (int i = 0;i < len - l;i ++){
int j = i + l;
for (int k = i + 1;k < j;k ++){
dp[i][j] = Math.max(dp[i][j],tmpnums[i] * tmpnums[k] * tmpnums[j] + dp[i][k] + dp[k][j]);
}
}
}
return dp[0][len - 1];
}
}

② D&C + Memorization，O(N^3) , O(N^2)

memorization是from top to bottom，每一次都将值分成两部分，然后分别计算。对于在left和right中间的位置i，考虑[left,i]和[i,right]能组成的部分，分别对这两部分进行递归求值。用二维数组记录已经计算过的值，避免重复计算。

class Solution { //10ms
public static int maxCoins(int[] nums) {
int[] tmpnums = new int[nums.length + 2];
for (int i = 1;i <= nums.length;i ++){
tmpnums[i] = nums[i - 1];
}
tmpnums[0] = 1;
tmpnums[tmpnums.length - 1] = 1;
int len = tmpnums.length;
int[][] memo = new int[len][len];
return burst(tmpnums,0,len - 1,memo);
}
public static int burst(int[] nums,int i,int j,int[][] memo){
if (i + 1 == j) return 0;//[i,j]之间没有ballon可以炸掉
if (memo[i][j] > 0){//如果已经计算过了，则直接返回
return memo[i][j];
}
int res = 0;
for (int k = i + 1;k < j;k ++){
res = Math.max(res,nums[i] * nums[k] * nums[j] + burst(nums,i,k,memo) + burst(nums,k,j,memo));//递归获取左右窗口的最大值
}
memo[i][j] = res;
return res;
}
}

### 叶枫啦啦

[LeetCode] Minimum Number of Arrows to Burst Balloons 最少数量的箭引爆气球

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it'......

2017/12/12
0
0
leetcode 452. Minimum Number of Arrows to Burst Balloons

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it'......

2017/09/30
0
0
ZOJ Problem Set - 2104 Let the Balloon Rise（map）

Let the Balloon Rise Time Limit: 2 Seconds Memory Limit: 65536 KB Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges' fa......

hushhw
2017/11/27
0
0
[Develop Game] AS3 Click the Balloons

MrLovelyCbb
2014/03/24
0
0

groovyland
2010/03/15
107
0

Quartz原理解析

Quartz原理解析 最近项目中好多地方都需要用到定时器，一开始用的是netty的hashWheel，后来发现删除任务的时候不是很好删除，于是就放弃了，然后选择了Quartz。 hashWheel定时器和Quartz的区...

46分钟前
1
0
explain详解

EXPLAIN列的解释 table 显示这一行的数据是关于哪张表的 type 这是重要的列，显示连接使用了何种类型。从最好到最差的连接类型为 const（读常量，最多只会有一条记录匹配，由于是常量，实际上...

50分钟前
1
0
Oracle 修改或新增数据后查不到数据

4
0
python学习整理(1)

#!/usr/bin/env python # -*- conding:utf-8 -*- 1、 python运算: + - * / % ** // In [21]: print(int(1.2)+3) 4 In [22]: print(float(1.2)+3) 4.2 In [15]: print(11//5) 2 In [16]: prin......

3
0
maven 在无法连接仓库的单机环境下打包程序

jingshishengxu

1
0