LeetCode 312. 戳气球

◎

本节目标

把最后戳破的气球留在区间末尾，枚举它带来的收益。

题意与约束

戳破气球会获得相邻未戳气球乘积的金币，求最大金币；调用后不能修改输入数组。

第一反应与重复子问题

直接决定第一步会改变邻居，状态不稳定；改为决定区间内最后戳哪个气球，边界邻居就固定了。

状态定义与转移推导

两端补虚拟值 1。dp[left][right] 表示开区间内的最大金币，枚举最后戳 last，收益为两侧子区间加 value[left]*value[last]*value[right]。

正确性依据

最后戳 last 时，开区间其余气球已经消失，因此它的两个相邻值恰为固定边界；所有最后选择均被枚举。

样例执行过程

[3,1,5,8] 补边界后逐步计算短开区间，完整开区间的最优值为 167。

代码实现

C++

C++17

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        vector<int> values{1};
        for (int value : nums) {
            values.push_back(value);
        }
        values.push_back(1);
        int n = static_cast<int>(values.size());
        vector<vector<int>> dp(n, vector<int>(n));
        for (int length = 2; length < n; length++) {
            for (int left = 0; left + length < n; left++) {
                int right = left + length;
                for (int last = left + 1; last < right; last++) {
                    dp[left][right] = max(
                        dp[left][right],
                        dp[left][last] + dp[last][right] + values[left] * values[last] * values[right]
                    );
                }
            }
        }
        return dp[0][n - 1];
    }
};

Python

Python 3

class Solution:
    def maxCoins(self, nums):
        values = [1, *nums, 1]
        n = len(values)
        dp = [[0] * n for _ in range(n)]
        for length in range(2, n):
            for left in range(n - length):
                right = left + length
                dp[left][right] = max(
                    dp[left][last] + dp[last][right] + values[left] * values[last] * values[right]
                    for last in range(left + 1, right)
                )
        return dp[0][n - 1]

复杂度分析

三层区间枚举，时间 O(n³)，空间 O(n²)。

边界与易错点

零值气球仍必须保留在状态中；使用新数组补边界，不能向传入的 nums 插入元素。

模式迁移

凡是“删除顺序改变邻居”的问题，都可尝试把第一步倒过来，枚举最后一次决策。回到区间动态规划。