312. 戳气球（区间dp）

article/2025/9/10 15:54:11

链接：https://leetcode-cn.com/problems/burst-balloons/

首先这个长度为500的范围可以猜测出是O(n^3)区间dp
这里主要讲述为什么状态定义要定义成开区间而不是闭区间

最大的原因：闭区间计算出来的状态是无法保证正确性的

假如使用一开始的闭区间定义去做：原先定义dp[i,j]：戳爆i~j下标气球的最大积分。

举一个样例：nums = [3,1,5,8]
（以下标开始为1进行讲述）

枚举k作为区间内最后一个被戳爆的气球，那么此时若最后一下要戳爆k，若想让k成为最后一下，则绿色部分要先消去完。

先考虑计算k为最后一个戳爆产生的积分，nums[i]*nums[k]*nums[j]，但是不止。因为此时戳爆后在[i,j]状态定义消去[i,j]所有气球，所以剩下的还有i,j两个气球的答案，因此如此定义这部分积分为:

 LL a = nums[k] * (nums[l] + nums[r]) + max(nums[l], nums[r]);LL b = nums[k] * nums[l] * nums[r] + nums[l] * nums[r] + max(nums[l], nums[r]);

我们再来看绿色部分：看起来直接加上dp[i+1,k-1]和dp[k+1,j-1]就行了。

那么dp[i+1,j-1]计算的时候是怎么计算的呢？

考虑绿1部分要消去完，肯定保证绿1要有最后一个被戳爆的气球，而该气球产生的积分要依赖nums[i]和nums[k]，分数为nums[x]*nums[i]*nums[k]。

也就是说我们现在计算dp[i,j]的时候要nums[i]和nums[j]的贡献，而dp[i+1,k-1]也要nums[i]和nums[j]的贡献，那我们dp[i+1,k-1]的这个答案就不是独立子问题的，和当前求解的状态仍然有共同的计算部分。

所以这个状态定义是有问题的。
在这里插入图片描述
具体来说：在计算[3,1,5,8]时，nums[k]=5时，计算出的结果为：1+0+3x8x5+3x8+8=152，这里可以发现少算，少算的部分是什么呢？我们看到计算dp[2][2]的时候答案是0，但是在实际上这个nums[2]=1戳破的时候是可以有旁边3x5的累加积分的，但是我们没算。这里就是问题。

而如果定义成开区间就没这样的问题。
当计算dp[i][j]的时候，nums[i]和nums[j]保证没有被戳破，而dp[i][k]的计算时保证nums[i+1]和nums[k-1]也存在，此时dp[i][j]通过dp[i][k]这部分直接转移过来是没有问题的，而且nums[k]的贡献直接和nums[i]，nums[j]相乘即可。
在这里插入图片描述

typedef long long LL;
class Solution {
public:static const int maxn = 510;LL dp[maxn][maxn];int maxCoins(vector<int>& nums) {int n = static_cast<int>(nums.size());nums.insert(nums.begin(), 1);nums.push_back(1);for (int i = 1; i <= n; i++) {dp[i][i] = nums[i];//dp[i][i] = nums[i - 1] * nums[i] * nums[i + 1];dp[i][i+1] = nums[i] * nums[i + 1] + max(nums[i], nums[i + 1]);    }for (int len = 3; len <= n; len++) {for (int l = 1; l + len - 1 <= n; l++) {int r = l + len - 1;//dp[l][r] = max(dp[l][r], nums[l - 1] * nums[l] * nums[r] + dp[l + 1][r - 1]);//dp[l][r] = max(dp[l][r], nums[r + 1] * nums[r] * nums[l] + dp[l + 1][r - 1]);for (int k = l + 1; k < r; k++) {LL a = nums[k] * (nums[l] + nums[r]) + max(nums[l], nums[r]);LL b = nums[k] * nums[l] * nums[r] + nums[l] * nums[r] + max(nums[l], nums[r]); dp[l][r] = max(dp[l][r], dp[l + 1][k - 1] + dp[k + 1][r - 1] + max(a, b));//cout << "dp["<<l<<"]"<<"["<<r<<"]="<<dp[l][r]<<endl;}}}return dp[1][n];//return dfs(0, n, nums);}
};

因此修改为开区间，dp状态转移就合理了。

typedef long long LL;
class Solution {
public:static const int maxn = 510;LL dp[maxn][maxn];int maxCoins(vector<int>& nums) {nums.insert(nums.begin(), 1);  nums.push_back(1);int n = static_cast<int>(nums.size());for (int len = 3; len <= n; len++) {for (int l = 0; l + len - 1 < n; l++) {int r = l + len - 1;for (int k = l + 1; k < r; k++) {dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + nums[l] * nums[r] * nums[k]);//cout << "dp["<<l<<"]"<<"["<<r<<"]="<<dp[l][r]<<endl;}}}return dp[0][n - 1];}
};