LeetCode 312. 戳气球

题面:https://leetcode-cn.com/problems/burst-balloons/

题意

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

现在要求你戳破所有的气球。
每当你戳破一个气球$i$时,你可以获得$ nums[left] \times nums[i] \times nums[right]$ 个硬币。 这里的$left$和$right$代表和$i$相邻的两个气球的序号。注意当你戳破了气球$i$后,气球$left$和气球$right$就变成了相邻的气球。
求所能获得硬币的最大数量。

解法

肯定是dp了。
而且是一个区间dp。令$dp[i][j]$表示戳破$i+1, i+2, …, j - 1$个气球
设$k$是$i$到$j$中最后一个被戳破的气球,则有

然后区间长度从小到大转移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int maxCoins(vector<int>& nums) {
int len = nums.size();
int dp[len + 10][len + 10] = {};
vector<int> a(len + 10);
a[0] = a[len + 1] = 1;
for(int i = 0; i < len; i++)
a[i + 1] = nums[i];
for(int l = 2; l <= len + 1; l++)
for(int i = 0, j = i + l; j <= len + 1; i++, j++)
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][len + 1];
}
};