312. 戳气球（区间dp）_打气球区间dp

链接：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]); 
1
2

我们再来看绿色部分：看起来直接加上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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

因此修改为开区间，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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22