​LeetCode刷题实战312:戳气球

程序IT圈

共 3219字,需浏览 7分钟

 ·

2021-07-04 09:02

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从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];
  }
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-280题汇总,希望对你有点帮助!

LeetCode刷题实战301:删除无效的括号

LeetCode刷题实战302:包含全部黑色像素的最小矩阵
LeetCode刷题实战303:区域和检索 - 数组不可变
LeetCode刷题实战304:二维区域和检索 - 矩阵不可变
LeetCode刷题实战305:岛屿数量II
LeetCode刷题实战306:累加数
LeetCode刷题实战307:区域和检索 - 数组可修改
LeetCode刷题实战308:二维区域和检索 - 可变
LeetCode刷题实战309:最佳买卖股票时机含冷冻期
LeetCode刷题实战310:最小高度树
LeetCode刷题实战311:稀疏矩阵的乘法

浏览 49
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报