【区间 DP】热门区间 DP 运用题

题目描述

这是 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

提示：

区间 DP

定义 为考虑将 范围内（不包含 l 和 r 边界）的气球消耗掉，所能取得的最大价值。

根据题意，我们可以对 nums 进行扩充，将其从长度为 的 nums 变为长度 的 arr，其中 对应了原数组 nums，而 。

此时易知 即是答案，不失一般性考虑 该如何转移，假设在 范围内最后剩下的气球的编号为 ，此时的 由「以 为分割点的两端所产生的价值」和「消耗 本身带来的价值」两部分组成：

为了确保转移能够顺利进行，我们需要确保在计算 的时候，区间长度比其小的 和 均被计算。

因此我们可以采用先枚举区间长度 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]
}

• 时间复杂度：
• 空间复杂度：

最后

这是我们「刷穿 LeetCode」系列文章的第 No.312 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库： 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉