LeetCode刷题实战312：戳气球 / 开普饭

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 戳气球，我们先来看题面：

https://leetcode-cn.com/problems/sparse-matrix-multiplication/

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

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

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

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

示例

示例 1：

输入：nums = [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

示例 2：

输入：nums = [1,5]
输出：10

解题

动态规划：

coins[i][j]表示的将下标(i,j)戳破可获得的最大值

coins[j][j+i] = max(coins[j][j+i], coins[j][k] + coins[k][j+i] + dpnums[j] * dpnums[k] * dpnums[j+i]);//k是(i,j)里面最后戳破的气球下标

class Solution {
public:
  int maxCoins(vector<int>& nums) {
    vector<int> dpnums(nums.size() + 2, 1);
    //将nums数组进行扩展[1，nums[0], nums[1], ... nums[n], 1]
    for(int i=0, j=1; i < nums.size(); i++, j++){
      dpnums[j] = nums[i];
    }
    vector<vector<int>> coins(dpnums.size(), vector<int>(dpnums.size(), 0));//coins[i][j]表示的将下标(i,j)戳破可获得的最大值
    int dpNumsSize = dpnums.size();
    for(int i = 2; i < dpNumsSize; i++) {
      for(int j = 0; j + i < dpNumsSize; j++) {
      //上面两层循环用于控制(j,i)的窗口的长度和移动
        //下面的循环用于穷举区间（i, j）中最后一个戳破的气球下标，从而确定窗口(i,j)戳破可得的最大值
        for(int k = j + 1; k < j + i; k++) {
          //coins[j][k] + coins[k][j+i]戳破（i，k）和（k，j）可获得的值
          //dpnums[j] * dpnums[k] * dpnums[j+i]戳破k可获得的值
          coins[j][j+i] = max(coins[j][j+i], coins[j][k] + coins[k][j+i] + dpnums[j] * dpnums[k] * dpnums[j+i]);
        }
      }
    }
    return coins[0][dpNumsSize - 1];
  }
};