312.burst-balloons.md

312. 戳气球

1. 描述

   • 有 n 个气球，编号为【0，n-1】，每个气球上都标有一个数字（在数组nums中）。
   • 要求戳破所有的气球。戳破气球i ，可以获得**nums[left] × nums[i] × nums[right]**个硬币。
   • left 和 right 代表和 i 相邻的两个气球的序号。当戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
   • 目标：求所能获得硬币的最大数量。
   • 说明：可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。

2. 思路

   • 问题转换
     • 观察戳气球的操作，这会导致两个气球从不相邻变成相邻，使得后续操作难以处理。
     • 倒过来看，将全过程看作每次添加一个气球。
   • 定义
     • 令dp[i][j]表示能填满开区间(i,j)得到的最多硬币数。
     • 最后返回return dp[0][orig_n+1]即可。
     • 为了方便操作，新建一个比nums长度多2的数组val, val两头元素是1, 中间元素复制nums。
   • 计算顺序
     • dp初始化为0。
     • 遍历起点i(倒序)，终点j，i和j之间位置k。
   • 转移方程
     • i ≥ j−1时，dp[i][j]=0。
     • i < j−1时，转移方程如下:
       • dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + val[i]*val[k]*val[j])

3. 实现

   class Solution {
   public:
       int maxCoins(vector<int>& nums) {
           int i,j,k;
           // 观察戳气球的操作，这会导致两个气球从不相邻变成相邻，使得后续操作难以处理。
           // 倒过来看，将全过程看作每次添加一个气球。
           // 令dp[i][j]表示能填满开区间(i,j)得到的最多硬币数。
           int orig_n = nums.size();
           vector<vector<int>> dp(orig_n+2, vector<int>(orig_n+2,0));
           // 新建一个比nums长度多2的数组val, val两头元素是1, 中间元素复制nums。
           vector<int> val(orig_n+2, 1);
           for(i=1; i<orig_n+1; i++)
               val[i] = nums[i-1];
   
           int sum;
           // 遍历起点i(倒序)，终点j，i和j之间位置k。
           for(i=orig_n+1-2; i>=0; i--){
               for(j=i+2; j<orig_n+2; j++){
                   for(k=i+1; k<j; k++){
                       // i≥j−1时，dp[i][j]=0。（初始化dp的时候全部是0）
                       // i<j−1时，转移方程如下。
                       sum=0;
                       sum += dp[i][k] + dp[k][j] + val[i]*val[k]*val[j];
                       dp[i][j] = max(dp[i][j], sum);
                   }
               }
           }
   
           return dp[0][orig_n+1];
       }
   };