有 n
个气球,编号为0
到 n - 1
,每个气球上都标有一个数字,这些数字存在数组 nums
中。现在要求戳破所有的气球。戳破第 i
个气球,可以获得 nums[i - 1] * nums[i] * nums[i + 1]
枚硬币。 这里的 i - 1
和 i + 1
代表和 i
相邻的两个气球的序号。如果 i - 1
或 i + 1
超出了数组的边界,那么就当它是一个数字为 1
的气球。
求所能获得硬币的最大数量。
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
示例 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
一道区间DP,在做的时候先考虑了闭区间,也就是 \(dp[i][j]\) 表示 戳掉了 \([i,j]\) 这个闭区间中所有气球得到的最大收益,递推公式如下:
\[dp[i][j]=dp[i][k-1]+dp[k+1][j]+a[k]*a[i-1]*a[j+1] \]这样做如果直接三层循环,在 \(i=j\) 以及 \(i=j-1\) 时,数组是不更新的,需要提前初始化;并且 \(k\) 选点的时候只会选取 \([i+1,j-1]\) 这个区间中的值,不会选到 \(i\) 或者 \(j\) ,但实际情况对于闭区间 \([i,j]\) 最后戳破的气球可能是这个闭区间上的任意一点。在此基础上继续修改会使代码变得更加复杂,于是改为下面开区间的做法:
\(dp[i][j]\) 表示戳掉开区间 \((i,j)\) 中所有气球得到的最大收益,最终结果为 \(dp[0][n+1]\)。递推公式为:
\[dp[i][j]=dp[i][k]+dp[k][j]+a[i]*a[k]*a[j] \]由于是开区间,\(i,j,k\) 都是之前未取到的,所以 \(dp[i][k]\) 和 \(dp[k][j]\) 可以无缝衔接,取 \(k\) 点的收益为 \(a[i]*a[k]*a[j]\) 。
其次在具体实现中,为不添加多余的边界特判,可以将 \(nums[0] \sim nums[n-1]\) 变到 \(a[1]\sim a[n]\) ,之后初始化 \(a[0]=a[n+1]=1\)。
具体代码如下:
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n=nums.size();
vector<int>a(n+2);
for(int i=0;i<n;i++)a[i+1]=nums[i];
vector<vector<int>>dp(n+2,vector<int>(n+2));
a[0]=a[n+1]=1;
for(int len=2;len<=n+1;len++){
for(int i=0;i<=n;i++){
int j=i+len;
if(j>n+1)break;
for(int k=i+1;k<j;k++)
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);
}
}
return dp[0][n+1];
}
};
标签:nums,int,--,开区间,动态,规划,气球,dp
From: https://www.cnblogs.com/sunmk/p/18527632