312. 戳气球（动态规划）

向右看齐 2023-10-05 19:41 5阅读 0赞

#### 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 的气球。

求所能获得硬币的最大数量。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

提示：

*  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.  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]
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];
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210215131050498.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210215133027723.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70