Burst Balloons

Q: 戳气球的时间复杂度是多少？

时间复杂度为 O(n³) ，空间复杂度为 O(n²) ：大约有 n²/2 个区间，每个区间都要尝试最多 n 个气球作为最后一个气球。对于 300 个气球，这大约需要 4.5 × 10^6 步。尝试所有顺序的时间复杂度为 O(n · n!) 。

Q: 能否用贪心顺序解决戳气球问题？

不行。先戳破最小的气球，在 [2, 4, 3] 中只能得到 24，而最高可以得到 33。每次都先戳破当前收益最高的气球，在 [2, 9, 2] 中可以得到 42，而先戳破一个 2 可以得到 18 + 18 + 9 = 45。每次戳破气球都会改变之后戳破气球的收益。

困难动态规划

+10

给定一排气球，用 nums 表示，其中 nums[i] 是气球 i 上的数字。你可以按任意顺序一次戳破一个气球，直到戳破所有气球。戳破一个气球可获得 left × nums[i] × right 枚硬币，其中 left 和 right 分别是它当前相邻气球上的数字，也就是仍在这一排中的最近左右气球。如果某一侧没有相邻气球，则该侧的数字按 1 计算。戳破气球后，它的两个相邻气球会变成相邻气球。返回你最多能获得多少枚硬币。

函数

maxCoins(nums: integer-array) → integer

numsinteger-array: 气球上的数字，从左到右
返回值integer: 戳破所有气球后，你最多能收集到的金币数

约束条件

1 ≤ nums.length ≤ 300
0 ≤ nums[i] ≤ 100
答案小于 3 × 10⁸，因此可以用 32 位有符号整数表示。

示例

输入: nums = [2, 4, 3]
输出: 33
解释: 让 4 爆裂，得到 2 × 4 × 3 = 24。现在 2 挨着 3，得分为 1 × 2 × 3 = 6，而 3 得 3 分：总共 33 分。

进阶

你还可以返回一个能赚取最多金币的爆发订单吗？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

每次戳破气球都会改变相邻关系，因此第一个戳破的气球不会把这一排分开：它两侧的气球会变成相邻气球。最后戳破的一段中的气球才会把这一排分开。它会留到最后，而其他气球都已被戳破，因此它两侧的区间彼此独立。对这些区间使用区间表，就能在 O(n³) 时间内解决这个问题。

尝试每一种爆裂顺序

结果正确，但无法在最大的测试中运行完毕

思路

选择一个气球，收集 left × value × right，移除它，再用相同的方法解决更短的一排气球，并在所有选择中保留最高总分。它会尝试每种顺序，因此结果正确。

第一次戳破有 n 种选择，接下来有 n-1 种，以此类推：共有 n! 种顺序，12 个气球时就已经有 479,001,600 种。记住每组剩余气球的结果也没有帮助，因为共有 2^n 组。

算法

编写 burstAll(row)，求 row 中气球能获得的最多金币，空行返回 0。
对于每个位置 k，获得 left × row[k] × right，越过任一端时使用 1，再加上移除 row[k] 后的行调用 burstAll 得到的金币。
返回所有 k 对应的最佳总金币数，并调用 burstAll(nums)。

def maxCoins(nums):
    # Most coins you can still collect from the balloons in row
    def burst_all(row):
        top = 0
        for k in range(len(row)):
            left = row[k - 1] if k > 0 else 1
            right = row[k + 1] if k + 1 < len(row) else 1
            # Burst row[k] now, then do as well as possible with the rest
            coins = left * row[k] * right + burst_all(row[:k] + row[k + 1:])
            top = max(top, coins)
        return top

    return burst_all(nums)

最后一个气球上的递归，使用备忘录

思路

在这一行两端各补上一个 1：vals = [1] + nums + [1]。补上的气球永远不会爆炸，它们代表缺失的邻居。设 solve(left, right) 表示两个仍然存在的位置之间的气球能获得的最多硬币。

假设这个区间中最后爆炸的是 k。区间中的其他气球爆炸时，k 就像一堵墙，因此 left 和 k 之间的部分只会看到自己的气球和两个固定边界，k 和 right 之间的部分也是如此。k 爆炸时，它的邻居恰好是 left 和 right。因此，对于每个 k，这个区间的最佳结果是两部分的最佳结果之和，再加上 vals[left] × vals[k] × vals[right]。答案就是两个补位气球之间这个区间的结果。大约有 n²/2 个区间，每个区间最多尝试 n 个气球，因此使用记忆化后，时间复杂度为 O(n³)。

算法

以 nums 为基础构建 vals，并在两端各加上 1，然后将 m 设为它的长度。
创建一个填满 -1 的 m × m 备忘录。
编写 solve(left, right)：如果 right - left < 2，则返回 0；如果已有存储值，则返回该值。
否则，将它们之间的每个 k 都尝试作为最后一个气球，保留最大的 solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right]，并存储该值。
返回 solve(0, m-1)。

def maxCoins(nums):
    # A 1 on each side stands for the ends of the row
    vals = [1] + nums + [1]
    m = len(vals)
    memo = [[-1] * m for _ in range(m)]

    # Most coins from the balloons strictly between left and right
    def solve(left, right):
        if right - left < 2:
            return 0
        if memo[left][right] >= 0:
            return memo[left][right]
        top = 0
        for last in range(left + 1, right):
            # last bursts after every other balloon in the gap
            coins = solve(left, last) + solve(last, right) + vals[left] * vals[last] * vals[right]
            top = max(top, coins)
        memo[left][right] = top
        return top

    return solve(0, m - 1)

按宽度填充区间表

思路

递归只会询问范围更小的区间，因此用循环填充同一张表，先处理较窄的区间，再处理较宽的区间。这样，较宽的区间需要用到 best[left][k] 和 best[k][right] 时，它们的值就已经确定了。

对于 [2, 4, 3]，补上边界后得到 [1, 2, 4, 3, 1]。best[0][4] 会尝试让每个气球最后被戳破。让 3 最后被戳破时，得到 best[0][3] = 30，再加上 1 × 3 × 1，总共是 33，是三种选择中最好的结果。

这种做法的计算量和记忆化版本相同，但普通循环省去了数百万次函数调用，因此在 Python 或 R 这类语言中，这个版本会快好几倍。

算法

在 nums 两端各添加一个 1，构造 vals，并将 m 设为它的长度。
创建一个填充为 0 的 m × m 表 best。
对于从 2 到 m-1 的每个宽度，以及数组中满足 right = left + width 的每个 left，尝试它们之间的每个 k。
将 best[left][right] 设为 best[left][k] + best[k][right] + vals[left] × vals[k] × vals[right] 中的最大值。
返回 best[0][m-1]。

def maxCoins(nums):
    # A 1 on each side stands for the ends of the row
    vals = [1] + nums + [1]
    m = len(vals)
    # best[left][right]: most coins from the balloons strictly between left and right
    best = [[0] * m for _ in range(m)]
    for width in range(2, m):
        for left in range(m - width):
            right = left + width
            edge = vals[left] * vals[right]
            top = 0
            for last in range(left + 1, right):
                # last goes after every other balloon in the gap,
                # so left and right are its neighbours when it bursts
                coins = best[left][last] + best[last][right] + edge * vals[last]
                if coins > top:
                    top = coins
            best[left][right] = top
    return best[0][m - 1]

易错点和边界情况

把第一次戳破的气球及其原始相邻气球一起计算，使用 nums[k-1] × nums[k] × nums[k+1]，再加上两侧的结果。这些相邻气球可能已经不在了：对于 [2, 4, 3]，这种算法会得出 44，比任何实际戳破顺序得到的结果都高。
按行填充表格，同时让 left 递增。这样，k > left 时的 best[k][right] 尚未计算，会被读取为 0。应按宽度填充，或者让 left 递减。
在备忘录中用 0 标记尚未求解的区间。值全为 0 的气球区间实际结果就是 0，因此每次访问时都会重新求解。应使用 -1。
在 Lua 和 R 中，填充后的位置范围是从 1 到 m，因此答案是 best[1][m]。

常见问题3

为什么 Burst Balloons 选择最后一个气球，而不是第一个？

第一个气球爆破后，它两侧的气球会成为邻居，因此仍会相互影响。某一段中的最后一个气球会在其他气球爆破时保留下来，因此它两侧的气球永远不会相遇，每一侧都是一个独立的子问题。当它爆破时，它的邻居就是这一段的边界。

戳气球的时间复杂度是多少？

时间复杂度为 O(n³)，空间复杂度为 O(n²)：大约有 n²/2 个区间，每个区间都要尝试最多 n 个气球作为最后一个气球。对于 300 个气球，这大约需要 4.5 × 10^6 步。尝试所有顺序的时间复杂度为 O(n · n!)。

能否用贪心顺序解决戳气球问题？

不行。先戳破最小的气球，在 [2, 4, 3] 中只能得到 24，而最高可以得到 33。每次都先戳破当前收益最高的气球，在 [2, 9, 2] 中可以得到 42，而先戳破一个 2 可以得到 18 + 18 + 9 = 45。每次戳破气球都会改变之后戳破气球的收益。

def maxCoins(nums):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

nums = [2, 4, 3]

预期输出