一、题目
有 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
二、思路——动态规划
对于求最值问题，我们想到回溯法和动态规划，这里我们用动态规划来解决。
定义状态：
题目中说你可以假设
n
u
m
s
[
−
1
]
=
n
u
m
s
[
n
]
=
1
nums[-1] = nums[n] = 1
nums[−1]=nums[n]=1，我们先把这两个边界加到数组中，形成一个新的长度为
n
+
2
n + 2
n+2 的数组 points，其中
p
o
i
n
t
s
[
0
]
=
p
o
i
n
t
s
[
n
+
1
]
=
1
points[0] = points[n + 1] = 1
points[0]=points[n+1]=1，那么我们要戳破的就是从 1 到
n
n
n 的所有气球。
我们要求的是戳破所有的气球能获得的硬币的最大数量，换句话说就是，戳破气球 0 和气球
n
+
1
n + 1
n+1 之间的气球能获得的硬币的最大数量。据此我们可以定义状态，
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 表示戳破气球 i 和气球 j 之间（开区间，不包括 i 和 j）的所有气球能获得的硬币的最大数量。
推导状态转移方程：
状态转移的过程其实就是我们在每一步怎么做选择的过程。现在要求
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]，假设我们每一步都选择戳破能够获得硬币数量最大的那个气球，最后只剩下一个气球的时候，没得选只能戳破该气球。所以我们要考虑的是气球 i 和 气球 j 之间最后被戳破的气球是哪个，不妨设为 k。那么戳破气球 k 能得到的金币数为
p
o
i
n
t
s
[
i
]
∗
p
o
i
n
t
s
[
k
]
∗
p
o
i
n
t
s
[
j
]
points[i] * points[k] * points[j]
points[i]∗points[k]∗points[j]，那
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 的值就是：
戳
破
(
i
,
k
)
之
间
的
气
球
获
得
的
最
大
硬
币
数
+
戳
破
(
k
,
j
)
之
间
的
气
球
获
得
的
最
大
硬
币
数
+
戳
破
气
球
k
获
得
的
硬
币
数
戳破(i, k)之间的气球获得的最大硬币数 + 戳破 (k,j)之间的气球获得的最大硬币数 + 戳破气球 k 获得的硬币数
戳破(i,k)之间的气球获得的最大硬币数+戳破(k,j)之间的气球获得的最大硬币数+戳破气球k获得的硬币数 即
d
p
[
i
]
[
j
]
=
d
p
[
i
]
[
k
]
+
d
p
[
k
]
[
j
]
+
p
o
i
n
t
s
[
i
]
∗
p
o
i
n
t
s
[
k
]
∗
p
o
i
n
t
s
[
j
]
dp[i][j] = dp[i][k] + dp[k][j] + points[i] * points[k] * points[j]
dp[i][j]=dp[i][k]+dp[k][j]+points[i]∗points[k]∗points[j] 其中
i
<
k
<
j
i <k < j
i<k<j。
意思就是，我们穷举
i
<
k
<
j
i <k < j
i<k<j，求出把每个 k 都看作最后一个戳破的气球时能获得的最大硬币数，选择硬币最多的方案。
遍历方向：
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 所依赖的状态是
d
p
[
i
]
[
k
]
dp[i][k]
dp[i][k] 和
d
p
[
k
]
[
j
]
dp[k][j]
dp[k][j]，那么我们必须保证：在计算
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]时，
d
p
[
i
]
[
k
]
dp[i][k]
dp[i][k] 和
d
p
[
k
]
[
j
]
dp[k][j]
dp[k][j] 已经被计算出来了（其中 i < k < j）。我们的目标是求出戳破所有的气球能获得的最大硬币数，即最后返回
d
p
[
0
]
[
n
+
1
]
dp[0][n + 1]
dp[0][n+1] 的值，由此看出 i 是从大到小的，j 是从小到大的。
边界条件：
数组初始化：当
j
≤
i
+
1
j \leq i +1
j≤i+1 时，
d
p
[
i
]
[
j
]
=
0
dp[i][j] = 0
dp[i][j]=0，因为此时
(
i
,
j
)
(i,j)
(i,j) 之间没有气球了。
三、代码
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
// 把两个虚拟气球添加到数组中
int[] points = new int[n + 2];
points[0] = points[n + 1] = 1;
for(int i = 1; i <= n; i++){
points[i] = nums[i - 1];
}
int[][] dp = new int[n + 2][n + 2];// 数组默认为0，不用再写初始化条件了
for(int i = n; i >= 0; i--){// i从大到小
for(int j = i + 1; j < n + 2; j++){// j从小到大
// 最后戳破的是哪个？选择硬币数最大的方案
for(int k = i + 1; k < j; k++){
dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + points[i] * points[k] * points[j]);
}
}
}
return dp[0][n + 1];
}
}
