Keshawn_lu's Blog

Leetcode 312. 戳气球

字数统计: 683阅读时长: 3 min
2020/07/19 Share

题目简介:

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

现在要求你戳破所有的气球。如果你戳破气球 i ,就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 leftright 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明:

  • 你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:

1
2
3
4
输入: [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[i][j]代表将开区间(i, j)内的所有气球戳爆后所能获得的最大硬币数量。

为处理边界问题,先将nums的最前面和最后面插入1。

由于是开区间,所以i的取值为0 ~ n - 1(n为没插入1前的数组长度),第一个气球为nums[0] = 1,最后一个气球为nums[n] = 1,所以若i >= n,则没有气球可以戳了。

j的取值为i + 2 ~ n + 1,若j < i + 2,则开区间里没有气球可以戳了。

所以在(i, j)区间里循环定义k,即k的取值为i + 1 ~ j - 1

k的左边最大硬币数为dp[i][k]k的右边最大硬币数为dp[k][j],将这些气球都戳爆后,最后戳nums[k]这个气球,获得的硬币数为nums[i] * nums[k] * nums[j]。(因为一定有一个是最后被戳爆的气球,所以循环遍历,找出硬币数最大值时的那个k即可)。

所以dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])

最后返回dp[0][n + 1],即不要最开始和最后面我们插入的那两个气球,只要中间的1,2, ..., n个气球。

tip:

  • i, j, k的边界值比较重要,需要理解清楚。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int maxCoins(vector<int>& nums) {

int n = nums.size();

nums.push_back(1);
nums.insert(nums.begin(), 1);

//(i, j)区间内,戳破所有气球所能获得的最大硬币数
vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));

for(int i = n - 1; i >= 0; i--){

for(int j = i + 2; j <= n + 1; j++){

for(int k = i + 1; k < j; k++){

int coins = nums[i] * nums[k] * nums[j];
//(i, k) + k + (k, j)
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + coins);
}
}
}

return dp[0][n + 1];
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: