题目
有 n 个气球，编号为0 到 n – 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i – 1]
*
nums[i]
*
nums[i + 1] 枚硬币。 这里的 i – 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i – 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例
输入：nums = [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
思路（动态规划）
-
每戳破一个气球
nu
m
s
[
i
]
nums[i]
n
u
m
s
[
i
]
，能获得的硬币数量就是
nu
m
s
[
i
−
1
]
∗
n
u
m
s
[
i
]
∗
n
u
m
s
[
i
+
1
]
nums[i-1] * nums[i] * nums[i+1]
n
u
m
s
[
i
−
1
]
∗
n
u
m
s
[
i
]
∗
n
u
m
s
[
i
+
1
]
为了考虑越界，就再开一个数组
ar
r
[
n
u
m
s
.
l
e
n
g
t
h
+
2
]
arr[nums.length+2]
a
r
r
[
n
u
m
s
.
l
e
n
g
t
h
+
2
]
，来存两个边界 1
-
我们可以枚举最后一个戳爆的气球
-
定义dp数组，
dp
[
i
]
[
j
]
dp[ i ][ j ]
d
p
[
i
]
[
j
]
表示 戳破
(i
,
j
)
(i,j)
(
i
,
j
)
之间的所有气球，
0<
=
i
<
n
+
1
0 <= i < n+1
0
<
=
i
<
n
+
1
-
注意如果
i<
=
j
i <= j
i
<
=
j
中间是没有气球的，因为是开区间所以k的左右两边的区间不会影响k
-
采用从下至上和从左往右的遍历方式
代码
class Solution {
public int maxCoins(int[] nums) {
int len = nums.length;
// 定义两个边界考虑到越界情况
int[] arr = new int[len+2];
// 越界只能获得1个硬币
arr[0] = arr[len+1] = 1;
for(int i = 1; i < len+1; i++) {
arr[i] = nums[i-1];
}
int[][] dp = new int[len+2][len+2];
// 从下往上枚举
for (int i = len+1; i >= 0; i--) {
// 从左往右枚举 （i < j）
for(int j = i+1; j < len+2; j++) {
// k要在（i,j）范围内
// 枚举最后一个戳爆的气球
for (int k = i + 1; k < j; k++) {
dp[i][j] = Math.max(dp[i][j],dp[i][k] + dp[k][j] + arr[i]*arr[k]*arr[j]);
}
}
}
return dp[0][len+1];
}
}