LeetCode 312. 戳气球

Categories:

题目描述
思路分析
1. 解法一：区间 DP（推荐）
相似题目

题目描述

✅ 312. 戳气球

思路分析

解法一：区间 DP（推荐）

核心思路：

在两端补上虚拟气球 1，令 val[0] = val[n+1] = 1。

设 dp[i][j] 表示戳破区间 (i, j) 内所有气球的最大硬币数。

枚举最后一个被戳破的气球 k，转移为 dp[i][k] + dp[k][j] + val[i] * val[k] * val[j]。

复杂度分析：

时间复杂度：O(n^3)，其中 n 为气球数量。

空间复杂度：O(n^2)，使用二维 DP 表。

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] val = new int[n + 2];
        val[0] = 1;
        val[n + 1] = 1;
        for (int i = 0; i < n; i++) {
            val[i + 1] = nums[i];
        }

        int[][] dp = new int[n + 2][n + 2];

        // 按区间长度递推
        for (int len = 2; len <= n + 1; len++) {
            for (int i = 0; i + len <= n + 1; i++) {
                int j = i + len;
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + val[i] * val[k] * val[j]);
                }
            }
        }

        return dp[0][n + 1];
    }
}

func maxCoins(nums []int) int {
    n := len(nums)
    val := make([]int, n+2)
    val[0] = 1
    val[n+1] = 1
    for i := 0; i < n; i++ {
        val[i+1] = nums[i]
    }

    dp := make([][]int, n+2)
    for i := 0; i < n+2; i++ {
        dp[i] = make([]int, n+2)
    }

    // 按区间长度递推
    for length := 2; length <= n+1; length++ {
        for i := 0; i+length <= n+1; i++ {
            j := i + length
            for k := i + 1; k < j; k++ {
                valGain := dp[i][k] + dp[k][j] + val[i]*val[k]*val[j]
                if valGain > dp[i][j] {
                    dp[i][j] = valGain
                }
            }
        }
    }

    return dp[0][n+1]
}

相似题目

题目	难度	考察点
1039. 多边形三角剖分的最低得分	中等	区间 DP
1130. 叶值的最小代价生成树	中等	区间 DP
375. 猜数字大小 II	中等	区间 DP
486. 预测赢家	中等	DP
1547. 切棍子的最小成本	困难	区间 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/20746903