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

题目描述

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`

解题思路

• 遍历区间长度 `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

Built with Hugo
Theme Stack designed by Jimmy