0%

[Leetcode]312. Burst Balloons(C++)

题目描述

题目链接:312. Burst Balloons

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

例子

例子 1

Input: nums = [3,1,5,8]
Output: 167
Explanation:
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

例子 2

Input: nums = [1,5]
Output: 10

Constraints

  • n == nums.length
  • 1 <= n <= 500
  • 0 <= nums[i] <= 100

解题思路

这种找最大值的方法通常可以试一下动态规划的思路,这里的状态可以是:一个区间内能拿到的最多硬币数,即 maxCoins[i][j] 表示从 ij 的最大硬币数,因此我们要求的实际上是 maxCoins[0][n - 1],为了方便表示以及考虑边界情况,可以在数组前后各添加 1,因此要求的变成 maxCoins[1][n],更新状态列表的顺序结合分而治之的思想,从小区间开始然后逐渐扩大,更新的逻辑为三重循环:

  • 遍历区间长度 len,从 1n
  • 给定区间长度的情况下,遍历区间左端点 left,从 1n - len + 1
  • 此时用于区间长度和左端点固定,因此右端点也是固定的:right = left + len - 1
  • 此外还需要遍历区间中剩下的气球 middleleftright
  • 气球爆炸顺序为: left to middle - 1 - middle + 1 to right (这两个顺序先后无所谓,爆破完后剩余中间的气球 middle,以及区间外的两个气球)
  • 状态更新方程为:
1
2
3
4
max_coins[left][right] = max(
max_coins[left][right],
max_coins[left][middle - 1] + max_coins[middle + 1][right]
+ nums[left - 1] * nums[middle] * nums[right + 1]);

完整代码为:

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
29
30
31
32
class Solution {
public:
int maxCoins(std::vector<int>& nums) {
int n = nums.size();
std::vector<std::vector<int>> max_coins(n + 2,
std::vector<int>(n + 2, 1));

for (int i = 1; i <= n; ++i) {
max_coins[i][i] = nums[i];
}

// interval length
for (int len = 1; len <= n; ++len) {
// left boundary of interval
for (int left = 0; left <= n - len + 1; ++left) {
// right boundary of interval
int right = left + len - 1;
// burst location in interval
for (int middle = left; middle <= right; middle++) {
// compare current result with result of bursting (left to
// middle - 1)->(middle + 1 to right)->middle
max_coins[left][right] = std::max(
max_coins[left][right],
max_coins[left][middle - 1] +
nums[left - 1] * nums[middle] * nums[right + 1] +
max_coins[middle + 1][right]);
}
}

return max_coins[1][n];
}
};
  • 时间复杂度: O(n^3)
  • 空间复杂度: O(n^2)

GitHub 代码同步地址: 312.BurstBalloons.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions