题目描述

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

现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

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

样例

[3,1,5,8]
167 

算法1

(区间dp) $O(n^3)$

一看题目就知道大致知道是区间dp,f[l][r]代表区间[l, r]的某种消去方式。问题在于如何定义这个状态。
如果无脑假设f[l][r]代表完全消去区间[l, r]的气球，然后枚举消去[l,r]中的第k个气球是会出问题的，因为k的状态转移取决于当前k左边未被消去的气球和右边未被消去的气球。而我们的状态定义显然无法记录这些信息。
因此在这题里，不妨设f[l, r]为消去[l + 1, r - 1]这段区间的气球(两个端点不消去)的最大分值.然后我们看最近一次的状态转移。应当注意到，无论我们我们怎么消法，最后一定是在[l, r]之间留下一个气球(设为k),把k消去后恰好得到当前状态。因此可得状态转移
f[l][r] = max(f[l][k] + f[k][r] + score[k] * score[l] * score[r]) (l < k < r)

时间复杂度

O(n ^ 3)

C++ 代码

class Solution {
    static constexpr int N = 510;
    int f[N][N];
    int scores[N];
    int n;
public:
    int maxCoins(vector<int>& nums) {
        n = nums.size();
        for(int i = 1;i <= n;i++) scores[i] = nums[i - 1];
        scores[0] = scores[n + 1] = 1;

        memset(f,0,sizeof f);

        for(int len = 3;len <= n + 2;len++)
            for(int l = 0;l + len - 1 <= n + 1;l++)
            {
                int r = l + len - 1;
                if(len == 3) f[l][r] = scores[l] * scores[l + 1] * scores[r];
                else {
                    for(int k = l + 1;k + 1 <= r;k++)
                        f[l][r] = max(f[l][r],f[l][k] + f[k][r] + scores[l] * scores[r] * scores[k]);
                }
            }

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