戳气球 - Stellar Observer Protocol

963 字

5 分钟

戳气球

2025-08-24

Algorithms

数组

/

动态规划

题目描述#

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

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

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

解题思路#

动态规划（区间DP）：
- 定义 dp[i][j] 为戳破区间 (i, j) 内气球能获得的最大硬币数
- 区间开区间处理，不包含边界气球
倒序思考：
- 考虑区间内最后戳破的气球 k
- 戳破 k 时获得 nums[i]*nums[k]*nums[j] 硬币
状态转移：
- dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])
- 枚举所有可能的 k
边界处理：
- 在数组两端添加虚拟气球 [1, ..., 1]
- 初始化长度为0的区间值为0

关键洞察#

动态规划（区间DP）：
- 定义 dp[i][j] 为戳破区间 (i, j) 内气球能获得的最大硬币数
- 区间开区间处理，不包含边界气球
倒序思考：
- 考虑区间内最后戳破的气球 k
- 戳破 k 时获得 nums[i]*nums[k]*nums[j] 硬币
状态转移：
- dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])
- 枚举所有可能的 k
边界处理：
- 在数组两端添加虚拟气球 [1, ..., 1]
- 初始化长度为0的区间值为0

复杂度分析#

指标	说明
时间复杂度	O(n³)：三重循环（长度、起点、分割点）
空间复杂度	O(n²)：二维DP表存储区间最优解
最优情况	O(n³)：无法低于立方复杂度

代码实现#

区间 DP

1
const maxCoins = (nums) => {
2
    const n = nums.length;
3
    // 添加首尾虚拟气球
4
    const balloons = [1, ...nums, 1];
5
    const m = balloons.length;
6

7
    // 初始化DP表
8
    const dp = Array.from({ length: m }, () => Array(m).fill(0));
9

10
    // 按区间长度枚举
11
    for (let len = 2; len < m; len++) {
12
        for (let i = 0; i < m - len; i++) {
13
            const j = i + len;
14
            // 枚举最后戳破的气球k
15
            for (let k = i + 1; k < j; k++) {
16
                const coins = dp[i][k] + dp[k][j] +
17
                            balloons[i] * balloons[k] * balloons[j];
18
                dp[i][j] = Math.max(dp[i][j], coins);
19
            }
20
        }
21
    }
22

23
    return dp[0][m - 1];
24
};

回溯

1
/**
2
 * @param {number[]} nums
3
 * @return {number}
4
 */
5
var maxCoins = function (nums) {
6
    const n = nums.length;
7
    const visited = Array.from({ length: n }, () => []);
8

9
    const helper = (begin, end) => {
10
        if (begin > end) {
11
            return 0;
12
        }
13

14
        if (visited[begin][end]) {
15
            return visited[begin][end]
16
        }
17

18
        let ans = 0;
19
        for (let i = begin; i <= end; i++) {
20
            let cur = nums[i];
21

22
            const left = helper(begin, i - 1);
23
            const right = helper(i + 1, end);
24

25
            if (begin - 1 >= 0) cur *= nums[begin - 1];
26
            if (end + 1 < n) cur *= nums[end + 1]
27

28
            ans = Math.max(ans, left + right + cur)
29
        }
30

31
        visited[begin][end] = ans;
32
        return ans;
33
    }
34

35
    return helper(0, n - 1);
36
};

实际应用场景#

最优拆除规划：建筑物拆除顺序优化（相邻建筑影响）`
化学链反应：分子链断裂能量最大化计算`
游戏策略：泡泡龙类游戏的最佳消除顺序`
生产流程：工序依赖型生产线的任务排序`

变种：输出最优戳破顺序#

1
const maxCoinsWithPath = (nums) => {
2
    const balloons = [1, ...nums, 1];
3
    const n = balloons.length;
4
    const dp = Array.from({ length: n }, () => Array(n).fill(0));
5
    const path = Array.from({ length: n }, () => Array(n).fill(-1));
6

7
    for (let len = 2; len < n; len++) {
8
        for (let i = 0; i < n - len; i++) {
9
            const j = i + len;
10
            for (let k = i + 1; k < j; k++) {
11
                const coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j];
12
                if (coins > dp[i][j]) {
13
                    dp[i][j] = coins;
14
                    path[i][j] = k; // 记录最后戳破的位置
15
                }
16
            }
17
        }
18
    }
19

20
    // 回溯重建路径
21
    const order = [];
22
    const buildPath = (i, j) => {
23
        if (i + 1 === j) return;
24
        const k = path[i][j];
25
        order.push(balloons[k]);
26
        buildPath(i, k);
27
        buildPath(k, j);
28
    };
29

30
    buildPath(0, n - 1);
31
    return { coins: dp[0][n - 1], order };
32
};