共计 1963 个字符，预计需要花费 5 分钟才能阅读完成。
题目形容
这是 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：
输出：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：
输出：nums = [1,5]
输入：10提醒：
- $n = nums.length$
- $1 <= n <= 300$
- $0 <= nums[i] <= 100$
区间 DP
定义 $f[l][r]$ 为思考将 $(l, r)$ 范畴内（不蕴含 l 和 r 边界）的气球消耗掉，所能获得的最大价值。
依据题意，咱们能够对 nums 进行裁减，将其从长度为 $n$ 的 nums 变为长度 $n + 2$ 的 arr，其中 $arr[1…n]$ 对应了原数组 nums，而 $arr[0] = arr[n + 1] = 1$。
此时易知 $f[0][n + 1]$ 即是答案，不失一般性思考 $f[l][r]$ 该如何转移，假如在 $(l, r)$ 范畴内最初剩下的气球的编号为 $k$，此时的 $f[l][r]$ 由「以 $k$ 为宰割点的两端所产生的价值」和「耗费 $k$ 自身带来的价值」两局部组成：
$$
f[l][r] = \max(f[l][k] + f[k][r] + arr[l] \times arr[k] \times arr[r]), k \in (l, r)
$$
为了确保转移可能顺利进行，咱们须要确保在计算 $f[l][r]$ 的时候，区间长度比其小的 $f[l][k]$ 和 $f[k][r]$ 均被计算。
因而咱们能够采纳先枚举区间长度 len，而后枚举区间左端点 l（同时间接算得区间右端点 r）的形式来做。
Java 代码：
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 代码：
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]
}- 工夫复杂度：$O(n^3)$
- 空间复杂度：$O(n^2)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.312 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
