题目描述

给定$n$个气球，标号从$0$到$n-1$。每一个气球上都画着一个数字，这组数字用数组$nums[]$表示。

要戳爆所有气球。如果戳气球$i$，那么会得到$nums[left] * nums[i] * nums[right]$个金币。这里$left$和$right$是$i$相邻的索引。戳完气球$i$，气球$left$和气球$right$会相邻。

目标是收集到最多的金币，通过选择最好的戳气球顺序。

注意：设定$num[-1] = nums[n] = 1, 0 <= n <= 500, 0 <= nums[i] <= 100$。

样例

Example 1:

输入: [3,1,5,8]
输出: 167
解释：
nums  = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

算法1

(动态规划) $O(n^3)$

状态： $dp[i][j]$表示戳爆从第$i$到第$j$个气球得到的最大金币数。

状态转移方程： $ dp[i][j] = max( dp[i][j], dp[i][k-1] + num[i-1] * nums[k] * nums[j+1] + dp[k+1][j] )$

其中，$k$可以理解成$[i,j]$范围里最后戳破的一个气球。

时间复杂度$O(n^3)$: 三层循环

空间复杂度$O(n^2)$: $dp[i][j]$数组的大小是$(n+2) * (n+2)$

C++ 代码

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(),1); //在nums最前面插入一个1，表示nums[-1]=1
        nums.push_back(1); //在nums最后面插入一个1，表示nums[n]=1
        vector<vector<int>> dp(n+2, vector<int>(n+2, 0)); //初始化dp数组


        for(int len=1; len<=n; ++len){
            for(int i=1; i<=n-len+1; ++i){
                int j = i+len-1;
                for(int k=i; k<=j; ++k){
                    dp[i][j] = max(dp[i][j], dp[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + dp[k+1][j]);
                }
            }
        }


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