【动态规划】LeetCode 312. 戳气球 --区间DP问题

article/2025/9/10 15:47:23

Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

🌈个人主页：主页链接

🌈算法专栏：专栏链接

我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接

目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

题目:戳气球

题解:

代码实现:

完结撒花

因为一些事,最近状态不是很好,加上今天的每日一题有点难,看的烦躁(就是菜 ,就来更新一下今天与每日一题相关的区间Dp问题(戳气球),这篇也是关于区间Dp的问题 uu可以看看

话不多说,开始!

题目:戳气球

题解:

这道题虽然被标为了Hard但依据Dp的特点,知道其中缘由之后也没有很难了.先来看看问题

有这样几个气球.我们要求出戳出他之后他掉落的最大金币数

例如,在戳掉1,则掉落的金币数为周围两个金币数相乘,再乘上被戳掉的气球的金币数

在思考dp问题的时候,我们需要将每一个子问题划分为不受周围影响的独立的子问题,所以观察我们刚刚的计算过程.我们发现,掉落的金币数与i j是有关系的

题目提到:如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

为了避免越界问题,那我们可以设定两个虚拟气球,他们得分都为1,这样可以将dp的子问题划分为

dp[i][j]的含义为:在i-1到j-1当中,戳破气球获得的最高分.

根据区间dp倒着推问题的特点:我们可以想想在i j当中,最后一个被戳爆的气球是哪一个.

其实每一个气球都能成为最后被戳破的那个,所以我们要做的就是在一定区间内去寻找,戳破这个气球,能获得最大收益的k值

若想要最后一个戳破k,则需要先将i-k的气球戳破,再将k-j的气球戳破,之后再将结果加上戳破k区间的值即可(注意k是最后一个戳爆的!!他的周围是没有球的,所以这就是为什么是独立的子问题的原因)

dp[i][j]=dp[i][k]+dp[k][j]+val[i]*val[j]*val[k]

观察发现,这是从小范围去推大范围,所以在计算大范围的时候,小范围一定是被准备好了.

所以从只有三个气球的区间开始计算,慢慢拓展到大的区间.存储每个区间可以获得的最大金币,留给之后计算

先看看Base Case是什么,当i j重合的时候,没有东西可以戳,此时得分为0

当我们计算任何一个Dp[i][j]的时候,我们希望dp[i][k] 与dp[k][j]都已经被计算出来了

所以我们一般采用,自底向上的遍历方法.

相关模板:

for(int i=n;i>=0;i--){for(int j=i+1;j<n;j++){for(int k=i+1;k<j;k++){..........}}}

也就是i从n开始到0结束,j从i+1开始小于n(这里的n是指不能取到额外给的那两个气球),而k介于这二者之间 ,为了避免越界问题,我们一般采用n+2的方法

代码实现:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Solution {
public:int maxCoins(vector<int>& nums) {vector<int>val(nums.size()+2);val[0]=val[val.size()-1]=1;for(int i=1;i<=nums.size();i++){val[i]=nums[i-1];}vector<vector<int>>dp(val.size(),vector<int>(val.size()));for(int i=val.size();i>=0;i--){for(int j=i+1;j<val.size();j++){for(int k=i+1;k<j;k++){dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+val[i]*val[j]*val[k]);}}}return dp[0][val.size()-1];}
};