312. 戳气球（动态规划）

312. 戳气球

• 题目
• 解题思路
• 代码

题目

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

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

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

提示：

• n == nums.length
• 1 <= n <= 500
• 0 <= nums[i] <= 100

解题思路

动态规划要求子问题之间要相互独立。但是这题每戳破一个气球，得到的硬币数量都和前后两个气球有关，所以必须巧妙的定义dp数组。

1. 首先我们我们定义出dp数组的含义：dp[i][j]=x ：戳破气球i和j之间（开区间，不包括i、j）的所有气球可获得的最大硬币数量为x

2. base case就是dp[i][j]=0。即默认可获得的硬币数量为0。

3. 那么我们要求的结果就是dp[0][n+1]

4. 下面我们还需要额外一步骤，往气球的首尾部，分别添加一个虚拟气球，形成一个新的气球队列。因为题目说如果 i \- 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。那我们干脆直接把边界加进去。

5. 我们这里如果正向思考，就只能写出回溯算法，肯定会超时。所以需要反向思考，(i,j)中最后被戳破的气球是哪一个？我们假设其为k，那么dp[i][j]应该为dp[i][k]+dp[k][j]+points[i]*points[j]*points[k](先戳破(i,k)的气球，再戳破(k,j)的气球，最后戳破k)。

6. 因为我们添加了虚拟气球，所以开区间（i,j）就刚好包含了原来要求的整个气球队列。

7. 根据dp数组，我们得出需要反向遍历

8. 

9. 所以我们只需要遍历，让每一个气球成为最后一个被戳破的气球，看那种情况得到的硬币数量最大就可以了。

代码

class Solution {
    public int maxCoins(int[] nums) {
        int n=nums.length;

        //添加两侧虚拟的气球
        int[] points=new int[n+2];
        points[0]=points[n+1]=1;//首尾两端添加的虚拟气球，硬币数量置为1

        for(int i=1;i<=n;i++){
            points[i]=nums[i-1];
        }

        //base case 已经都被初始化为0
//dp[i][j]=x：戳破气球i和j之间（开区间，不包括i、j）的所有气球可获得的最大硬币数量为x
        int dp[][]=new int[n+2][n+2];

        for(int i=n+1;i>=0;i--){
            for(int j=i;j<n+2;j++){
                //k：开区间(i,j)中最后被戳破的那个气球
                /*
                dp[i][k]+dp[k][j]+points[i]*points[j]*points[k]：
                先戳破(i,k)的气球，再戳破(k,j)的气球，最后戳破k
                */
                for(int k=i+1;k<j;k++){
                    dp[i][j]=Math.max(dp[i][j],
                    dp[i][k]+dp[k][j]+points[i]*points[j]*points[k]);
                }
            }
        }
    return dp[0][n+1];
    }

}