leetcode312 戳气球（hard）

题目

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

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

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

说明:

你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:

输入: [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：暴力递归

时间会超时

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        // 在输入的头尾插入1，可以处理边界情况
        nums.insert(nums.begin(),1);
        nums.push_back(1);
 
        return getMaxCoins(nums,1,n);
    }
 
    // 获得l和r之间最大的分数，包括l和r
    int getMaxCoins(vector<int>& nums,int l,int r){
        // l和r相等时,l和r范围只有1个气球，之间打爆
        if(l == r) return nums[l-1]*nums[l]*nums[l+1];
        // 最后打掉的为l或者r时，最后打掉的点的分数是和l-1,r+1的分数相乘
        int max_coins = max(nums[l-1]*nums[l]*nums[r+1]+getMaxCoins(nums,l+1,r),
                            nums[l-1]*nums[r]*nums[r+1]+getMaxCoins(nums,l,r-1));
 
        // 最后打掉的为l和r之间的点时
        for(int k = l+1;k < r;k++){
            max_coins = max(max_coins,nums[l-1]*nums[k]*nums[r+1]+getMaxCoins(nums,l,k-1)+getMaxCoins(nums,k+1,r));
        }
        return max_coins;
    }
};

思路2：dp

其实只是把上面的递归，写成了dp，这样可以省去很多重复的计算，因此不会超时

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = int(nums.size());
        if(n == 0) return 0;
        // 在输入的头尾插入1，可以处理边界情况
        nums.insert(nums.begin(),1);
        nums.push_back(1);
 
        // dp[i][j]：i到j之间打爆的最大分数，包括i,j
        vector<vector<int>> dp(n+1,vector<int>(n+1,0));
        // i==j情况
        for(int i = 1;i <= n;i++){
            dp[i][i] = nums[i-1]*nums[i]*nums[i+1];
        }
        // 注意这里遍历方法
        // dp[i][j]需要用到的dp[i][k-1]+dp[k-1][j]，分别位置[i][j]位置的左边和下边
        // 所以这里从下往上，从左往右遍历
        for(int i = n-1;i >= 1;i--){
            for(int j = i+1;j <= n;j++){
                dp[i][j] = max(dp[i+1][j]+nums[i-1]*nums[i]*nums[j+1],
                               dp[i][j-1]+nums[i-1]*nums[j]*nums[j+1]);
                for(int k = i+1;k < j;k++){
                    dp[i][j] = max(dp[i][j],dp[i][k-1]+dp[k+1][j]+nums[i-1]*nums[k]*nums[j+1]);
                }
            }
        }
        return dp[1][n];
    }
};