LeetCode 312. 戳气球（DP，难）

1. 题目

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

现在要求你戳破所有的气球。每当你戳破一个气球 i 时，你可以获得 n u m s [ l e f t ] ∗ n u m s [ i ] ∗ n u m s [ r i g h t ] nums[left] * nums[i] * nums[right] 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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/burst-balloons 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. DP解题

看的别人的解题思路

• d p [ i ] [ j ] dp[i][j] dp[i][j] 表示戳破 i 到 j 的气球获得的最大金币
• 每次戳破气球的顺序会影响后面的结果，直接求解的复杂度是 O ( n ! ) O(n!) O(n!)
• 逆向思考，假设最后戳破 k 号气球，那么 k 号气球左边和右边的求解是互不干扰的
• d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i ] [ k − 1 ] + n u m s [ i − 1 ] ∗ n u m s [ k ] ∗ n u m s [ j + 1 ] + d p [ k + 1 ] [ j ] ) dp[i][j] = max(dp[i][j],\quad dp[i][k-1]+nums[i-1]*nums[k]*nums[j+1]+dp[k+1][j]) dp[i][j]=max(dp[i][j],dp[i][k−1]+nums[i−1]∗nums[k]∗nums[j+1]+dp[k+1][j])
• [ i , j ] [i,j] [i,j] 有多少种组合呢，用他们的长度 l e n len len 表示， 1 < = l e n < = n 1<=len<=n 1<=len<=n
• 在长度len下，i，j 窗口遍历数组，在 i，j 窗口内用递推公式求 d p [ i ] [ j ] dp[i][j] dp[i][j]

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(),1);//首尾加入虚拟的气球
        nums.push_back(1);
        vector<vector<int>> dp(n+2,vector<int>(n+2,0));
        int len, i, j, k;
        for(len = 1; len <= n; ++len) 
        {
        	for(i = 1; i <= n-len+1; ++i)
        	{
        		j = len+i-1;
        		for(k = i; 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];
    }
};