返回

[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,以及区间外的两个气球)
  • 状态更新方程为:
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

Built with Hugo
Theme Stack designed by Jimmy