题目描述
这是 LeetCode 上的「312. 戳气球」，难度为「困难」。
Tag : 「区间 DP」、「动态规划」
有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i 1] 枚硬币。 这里的 i - 1 和 i 1 代表和 i 相邻的两个气球的序号。
如果 i - 1 或 i 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1：
代码语言：javascript复制输入：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
示例 2：
代码语言：javascript复制输入：nums = [1,5]
输出：10
提示：
区间 DP
定义
为考虑将
范围内（不包含 l 和 r 边界）的气球消耗掉，所能取得的最大价值。
根据题意，我们可以对 nums 进行扩充，将其从长度为
的 nums 变为长度
的 arr，其中
对应了原数组 nums，而
。
此时易知
即是答案，不失一般性考虑
该如何转移，假设在
范围内最后剩下的气球的编号为
，此时的
由「以
为分割点的两端所产生的价值」和「消耗
本身带来的价值」两部分组成：
为了确保转移能够顺利进行，我们需要确保在计算
的时候，区间长度比其小的
和
均被计算。
因此我们可以采用先枚举区间长度 len，然后枚举区间左端点 l（同时直接算得区间右端点 r）的方式来做。
Java 代码：
代码语言：javascript复制class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] arr = new int[n 2];
arr[0] = arr[n 1] = 1;
for (int i = 1; i <= n; i ) arr[i] = nums[i - 1];
int[][] f = new int[n 2][n 2];
for (int len = 3; len <= n 2; len ) {
for (int l = 0; l len - 1 <= n 1; l ) {
int r = l len - 1;
for (int k = l 1; k <= r - 1; k ) {
f[l][r] = Math.max(f[l][r], f[l][k] f[k][r] arr[l] * arr[k] * arr[r]);
}
}
}
return f[0][n 1];
}
}
TypeScript 代码：
代码语言：javascript复制function maxCoins(nums: number[]): number {
const n = nums.length
const arr = new Array<number>(n 2).fill(1)
for (let i = 1; i <= n; i ) arr[i] = nums[i - 1]
const f = new Array<Array<number>>(n 2)
for (let i = 0; i < n 2; i ) f[i] = new Array<number>(n 2).fill(0)
for (let len = 3; len <= n 2; len ) {
for (let l = 0; l len - 1 <= n 1; l ) {
const r = l len - 1
for (let k = l 1; k <= r - 1; k ) {
f[l][r] = Math.max(f[l][r], f[l][k] f[k][r] arr[l] * arr[k] * arr[r])
}
}
}
return f[0][n 1]
}
- 时间复杂度：
- 空间复杂度：
