戳气球问题（气球爆炸后相邻气球合并的新值计算）

字数 2494 2025-12-08 03:22:49

戳气球问题（气球爆炸后相邻气球合并的新值计算）

题目描述
你有 n 个气球，从左到右排列，每个气球上标有一个正整数。你被要求戳破所有气球，戳破第 i 个气球可以获得一定的得分。得分的计算规则如下：

假设你戳破的气球是第 i 个（索引从 0 开始），它的得分为：nums[left] * nums[i] * nums[right]，其中 nums[left] 和 nums[right] 分别是第 i 个气球左边和右边相邻的、尚未被戳破的气球上的数字。
如果左边没有尚未被戳破的气球，则 nums[left] = 1；如果右边没有，则 nums[right] = 1。
戳破第 i 个气球后，它被移除，其左右相邻的气球会变成彼此相邻。
你的目标是计算戳破所有气球能获得的最大总得分。

输入格式
一个整数数组 nums，长度 n 满足 1 ≤ n ≤ 500，每个元素 0 ≤ nums[i] ≤ 100。

输出格式
一个整数，表示最大得分。

示例
输入：nums = [3,1,5,8]
输出：167
解释：
一种最优戳法（下标从 1 开始标记气球）：

戳气球 3（值 1），得分 = 3 * 1 * 5 = 15，数组变为 [3,5,8]
戳气球 2（值 5），得分 = 3 * 5 * 8 = 120，数组变为 [3,8]
戳气球 1（值 3），得分 = 1 * 3 * 8 = 24，数组变为 [8]
戳气球 4（值 8），得分 = 1 * 8 * 1 = 8
总得分 = 15 + 120 + 24 + 8 = 167

解题过程循序渐进讲解

第一步：问题转化与状态定义
直接按戳破顺序思考会难以处理，因为戳破一个气球后数组会变化，相邻关系动态改变。我们可以反过来思考：考虑最后一个被戳破的气球。
假设最后戳破的是第 k 个气球（在原数组中的位置），那么：

在戳破它之前，它左侧的所有气球（一个连续区间）和右侧的所有气球（另一个连续区间）都已经被戳破了。
戳破它时，它的左边相邻气球是整个区间左侧边界外的气球，右边相邻气球是整个区间右侧边界外的气球（因为区间内气球已戳完）。
因此，问题可以转化为：在数组两端添加虚拟气球，值为 1，然后考虑戳破某个区间内所有气球，最后戳破区间中某个气球，从而将大区间拆分成两个独立子区间。这符合区间动态规划的思路。

定义数组 a 长度为 n+2，其中 a[0] = a[n+1] = 1，a[1..n] 为原 nums。
定义 dp[l][r] 表示戳破区间 (l, r) 内所有气球（即下标从 l+1 到 r-1 的气球）能获得的最大得分，其中 l 和 r 是区间边界，不戳破。
最终答案是 dp[0][n+1]，即戳破 (0, n+1) 内（也就是原所有气球）的最大得分。

第二步：状态转移方程推导
考虑区间 (l, r)，我们需要戳破这个区间内所有气球。假设最后一个戳破的是中间某个气球 k（l < k < r），那么：

在戳破 k 之前，区间 (l, k) 和 (k, r) 内的所有气球都已经被戳破了。
戳破 k 时，它的左边相邻气球是 a[l]，右边相邻气球是 a[r]（因为区间内已空），所以得分为 a[l] * a[k] * a[r]。
戳破区间 (l, k) 和 (k, r) 的得分分别是 dp[l][k] 和 dp[k][r]，且这两部分独立（因为 k 最后戳，分隔了左右）。

因此，对区间 (l, r)，枚举最后一个戳破的 k，有：

dp[l][r] = max_{k = l+1 .. r-1} ( dp[l][k] + dp[k][r] + a[l] * a[k] * a[r] )

其中，如果区间内没有气球（即 l+1 == r），则 dp[l][r] = 0。

第三步：计算顺序与初始化
由于 dp[l][r] 依赖于更小的区间（(l, k) 和 (k, r) 都比 (l, r) 短），我们需要按区间长度从小到大计算。
区间长度 len 从 2 开始到 n+2（因为边界 l 和 r 之间至少有一个位置 k 才是非空区间）。

初始化：对所有 l，dp[l][l+1] = 0（区间内无气球）。
递推：对每个 l，r = l + len，枚举 k ∈ (l, r) 更新 dp[l][r]。

第四步：示例演算
以 nums = [3,1,5,8] 为例，a = [1,3,1,5,8,1]，n=4。
计算过程（只展示关键步骤）：

长度 len=2：区间如 (0,2) 内只有气球 1（值 3），dp[0][2] = a[0]*a[1]*a[2] = 1*3*1=3。
长度 len=3：如 (0,3) 内有气球 1,2（值 3,1），枚举最后戳破的 k：
- k=1：得分 = dp[0][1] + dp[1][3] + a[0]*a[1]*a[3] = 0 + 0 + 1*3*5 = 15
- k=2：得分 = dp[0][2] + dp[2][3] + a[0]*a[2]*a[3] = 3 + 0 + 1*1*5 = 8
  取最大值 15，即 dp[0][3]=15。
依此类推，最终 dp[0][5] 即为整个区间的最大得分 167。

第五步：复杂度分析

时间复杂度：O(n³)，因为三层循环：区间长度 O(n)，左端点 O(n)，枚举中间点 O(n)。
空间复杂度：O(n²)，存储 dp 表。

第六步：核心要点总结

关键思路是逆向思考最后戳破的气球，从而将问题分解为两个独立子区间。
添加边界虚拟气球（值为 1）简化边界处理。
状态定义时区间为开区间 (l, r)，表示只戳破内部气球，l 和 r 不戳。
按区间长度从小到大的顺序进行动态规划。

你可以尝试实现这个算法，并验证示例结果。

戳气球问题（气球爆炸后相邻气球合并的新值计算）题目描述你有 n 个气球，从左到右排列，每个气球上标有一个正整数。你被要求戳破所有气球，戳破第 i 个气球可以获得一定的得分。得分的计算规则如下：假设你戳破的气球是第 i 个（索引从 0 开始），它的得分为： nums[left] * nums[i] * nums[right] ，其中 nums[left] 和 nums[right] 分别是第 i 个气球左边和右边相邻的、尚未被戳破的气球上的数字。如果左边没有尚未被戳破的气球，则 nums[left] = 1 ；如果右边没有，则 nums[right] = 1 。戳破第 i 个气球后，它被移除，其左右相邻的气球会变成彼此相邻。你的目标是计算戳破所有气球能获得的最大总得分。输入格式一个整数数组 nums ，长度 n 满足 1 ≤ n ≤ 500 ，每个元素 0 ≤ nums[i] ≤ 100 。输出格式一个整数，表示最大得分。示例输入： nums = [3,1,5,8] 输出：167 解释：一种最优戳法（下标从 1 开始标记气球）：戳气球 3（值 1），得分 = 3 * 1 * 5 = 15，数组变为 [ 3,5,8 ] 戳气球 2（值 5），得分 = 3 * 5 * 8 = 120，数组变为 [ 3,8 ] 戳气球 1（值 3），得分 = 1 * 3 * 8 = 24，数组变为 [ 8 ] 戳气球 4（值 8），得分 = 1 * 8 * 1 = 8 总得分 = 15 + 120 + 24 + 8 = 167 解题过程循序渐进讲解第一步：问题转化与状态定义直接按戳破顺序思考会难以处理，因为戳破一个气球后数组会变化，相邻关系动态改变。我们可以反过来思考：考虑最后一个被戳破的气球。假设最后戳破的是第 k 个气球（在原数组中的位置），那么：在戳破它之前，它左侧的所有气球（一个连续区间）和右侧的所有气球（另一个连续区间）都已经被戳破了。戳破它时，它的左边相邻气球是整个区间左侧边界外的气球，右边相邻气球是整个区间右侧边界外的气球（因为区间内气球已戳完）。因此，问题可以转化为：在数组两端添加虚拟气球，值为 1，然后考虑戳破某个区间内所有气球，最后戳破区间中某个气球，从而将大区间拆分成两个独立子区间。这符合区间动态规划的思路。定义数组 a 长度为 n+2 ，其中 a[0] = a[n+1] = 1 ， a[1..n] 为原 nums 。定义 dp[l][r] 表示戳破区间 (l, r) 内所有气球（即下标从 l+1 到 r-1 的气球）能获得的最大得分，其中 l 和 r 是区间边界，不戳破。最终答案是 dp[0][n+1] ，即戳破 (0, n+1) 内（也就是原所有气球）的最大得分。第二步：状态转移方程推导考虑区间 (l, r) ，我们需要戳破这个区间内所有气球。假设最后一个戳破的是中间某个气球 k （ l < k < r ），那么：在戳破 k 之前，区间 (l, k) 和 (k, r) 内的所有气球都已经被戳破了。戳破 k 时，它的左边相邻气球是 a[l] ，右边相邻气球是 a[r] （因为区间内已空），所以得分为 a[l] * a[k] * a[r] 。戳破区间 (l, k) 和 (k, r) 的得分分别是 dp[l][k] 和 dp[k][r] ，且这两部分独立（因为 k 最后戳，分隔了左右）。因此，对区间 (l, r) ，枚举最后一个戳破的 k ，有：其中，如果区间内没有气球（即 l+1 == r ），则 dp[l][r] = 0 。第三步：计算顺序与初始化由于 dp[l][r] 依赖于更小的区间（ (l, k) 和 (k, r) 都比 (l, r) 短），我们需要按区间长度从小到大计算。区间长度 len 从 2 开始到 n+2 （因为边界 l 和 r 之间至少有一个位置 k 才是非空区间）。初始化：对所有 l ， dp[l][l+1] = 0 （区间内无气球）。递推：对每个 l ， r = l + len ，枚举 k ∈ (l, r) 更新 dp[l][r] 。第四步：示例演算以 nums = [3,1,5,8] 为例， a = [1,3,1,5,8,1] ， n=4 。计算过程（只展示关键步骤）：长度 len=2 ：区间如 (0,2) 内只有气球 1（值 3）， dp[0][2] = a[0]*a[1]*a[2] = 1*3*1=3 。长度 len=3 ：如 (0,3) 内有气球 1,2（值 3,1），枚举最后戳破的 k ： k=1 ：得分 = dp[0][1] + dp[1][3] + a[0]*a[1]*a[3] = 0 + 0 + 1*3*5 = 15 k=2 ：得分 = dp[0][2] + dp[2][3] + a[0]*a[2]*a[3] = 3 + 0 + 1*1*5 = 8 取最大值 15，即 dp[0][3]=15 。依此类推，最终 dp[0][5] 即为整个区间的最大得分 167。第五步：复杂度分析时间复杂度：O(n³)，因为三层循环：区间长度 O(n)，左端点 O(n)，枚举中间点 O(n)。空间复杂度：O(n²)，存储 dp 表。第六步：核心要点总结关键思路是逆向思考最后戳破的气球，从而将问题分解为两个独立子区间。添加边界虚拟气球（值为 1）简化边界处理。状态定义时区间为开区间 (l, r) ，表示只戳破内部气球， l 和 r 不戳。按区间长度从小到大的顺序进行动态规划。你可以尝试实现这个算法，并验证示例结果。