题目描述
题目链接:312. Burst Balloons
You are given
n
balloons, indexed from0
ton - 1
. Each balloon is painted with a number on it represented by an arraynums
. You are asked to burst all the balloons.If you burst the
ith
balloon, you will getnums[i - 1] * nums[i] * nums[i + 1]
coins. Ifi - 1
ori + 1
goes out of bounds of the array, then treat it as if there is a balloon with a1
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]
表示从 i
到 j
的最大硬币数,因此我们要求的实际上是 maxCoins[0][n - 1]
,为了方便表示以及考虑边界情况,可以在数组前后各添加 1
,因此要求的变成 maxCoins[1][n]
,更新状态列表的顺序结合分而治之的思想,从小区间开始然后逐渐扩大,更新的逻辑为三重循环:
- 遍历区间长度
len
,从1
到n
- 给定区间长度的情况下,遍历区间左端点
left
,从1
到n - len + 1
- 此时用于区间长度和左端点固定,因此右端点也是固定的:
right = left + len - 1
- 此外还需要遍历区间中剩下的气球
middle
从left
到right
- 气球爆炸顺序为:
left to middle - 1
-middle + 1 to right
(这两个顺序先后无所谓,爆破完后剩余中间的气球middle
,以及区间外的两个气球) - 状态更新方程为:
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]);
完整代码为:
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