LeetCode 312 戳气球

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

原先第一反应是贪心, 但是发现模拟样例也不对 —— 假设每次选取收益最高的, 会破坏周围的气球“邻居关系”, 而且每次戳破的时候可能会“消灭”掉最大数字的气球,导致它的贡献变少(它可能会在未来做出大贡献, 但却从当前序列中离开)

所以无法使用贪心, 但是动态规划也不容易想到 —— 假设按照题目模拟的正向思路, 每次选取第 i 个气球戳破, 那么对于当前的收益, 我们不仅需要知道第 i 个气球的位置, 还需要维护它的左右邻居的关系, 同时每次戳破气球都会使得邻居关系被破坏. 导致无法拆分成独立子问题

感觉也非常复杂. (所以暴力搜索, 直接枚举所有情况)

那么反过来想, 假设枚举中间要戳的气球不行, 不妨思考能否通过枚举两侧区间来进行 —— 对于一个确定 L 和 R 的区间, 其内部一定有一个气球是最后戳破的, 使得大区间变成 L K R, 此时区间的贡献就是一定的了 —— 最后戳破 K. 那么在(L, K) 和 (K, R) 这两个区间中, 如果戳破所有的气球,也可以有类似逻辑. 这样我们就结束了拆分“最优子结构”的事情.

综上, 不妨定义 —— dp[L][R] 为在开区间 (L, R) 中, 戳破所有的气球所获得的最高收益, 那么我们可以在区间内枚举 K, 得到

$$dp[L][R]=max\{dp[L][K]+dp[K][R]+nums[L]\ast nums[K]\ast nums[R]\}$$

其中 L < K < R.

以及可以发现,在求取 dp[L][R] 的时候, 它依赖区间长度更短的 dp[L'][R'] 所以在枚举得到 dp[L][R] 的时候, 需要从小到大枚举长度, 再进行计算.