力扣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 的气球。
求所能获得硬币的最大数量。
输入输出样例
输入: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
输入:nums = [1,5]
输出:10
解法,动态规划
int maxCoins(vector<int>&nums)
{
//使用动态规划的思想,从底向上进行实现
//首先创建头尾都为1的辅助数组,方便结果的计算
int length=nums.size();
vector<int>tempArr(length+2,1);
//创建二维动态规划数组
vector<vector<int>>dp(length+2,vector<int>(length+2,0));
//初始化辅助数组,将num的值拷贝到对应的tempArr中去
for(int i=1;i<=length;i++)
{
tempArr[i]=nums[i-1];
}
//建立状态转移方程
//设置初始区间为3,表示开区间的长度,对每一个区间长度进行循环
for(int len=3;len<=length+2;len++)
{
//i表示区间的左端点
for(int i=0;i<=length+2-len;i++)
{
int res=0;
//k表示开区间内的索引(代表区间最后一个被戳破的气球),i+len-1,表示区间的右端点
for(int k=i+1;k<i+len-1;k++)
{
//left,right分别代表左区间和右区间
int left=dp[i][k];
int right=dp[k][i+len-1];
int tempSum=tempArr[k]*tempArr[i]*tempArr[i+len-1];
int sum=left+right+tempSum;
//逐个取金币的最大值
dp[i][i+len-1]=max(dp[i][i+len-1],sum);
}
}
}
return dp[0][length+1];
}