小旭解说算法之路 LeetCode 312 封面
小旭解说算法之路 LeetCode 312 封面

BiliBili

YouTube

原题

中文

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

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

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

说明:

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

英文

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

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

Note:

  • You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Input: [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

思路

解法一 回溯法

                         3 1 5
                 /   	   |        \
              1 5         3 5         3 1          3(n)
           /     \      /     \     /     \ 
         5        1   5        3   1        3      2(n - 1)

方案总数:n * (n - 1) * (n - 2) * … * 1 = n!

函数调用次数: 1 + n + n * (n - 1) + n * (n - 1) * (n - 2) + … + n!

超时

代码

class Solution {
private:
    void helper(vector<int>& nums, int coins, int& ans) {
        // boundary
        if (nums.size() == 0) {
            ans = max(ans, coins);
            return;
        }
        // search
        for (int i = 0; i < nums.size(); ++i) {
            int tmp = nums[i];
            int delta = nums[i] * (i - 1 < 0 ? 1 : nums[i - 1]) * (i + 1 > nums.size() - 1 ? 1 : nums[i + 1]);
            nums.erase(nums.begin() + i);
            helper(nums, coins + delta, ans);
            nums.insert(nums.begin() + i, tmp);
        }
    }
public:
    int maxCoins(vector<int>& nums) {
        int ans = 0;
        helper(nums, 0, ans);
        return ans;
    }
};

解法二 动态规划——记忆化递归(备忘录法)

分析最优子结构

正向思考

[3, 1, 5] 为例,对于第一次选择,我们有三种选择。

选择 3 将问题分解为左边的子问题: [] 和 右边子问题: [1, 5]

其解等于: [] + [1, 5] + 1 * 3 * 1

选择1 将问题分解为左边的子问题: [3] 和 右边子问题: [5]

其解等于: [3] + [5] + 3 * 1 * 5

选择5 将问题分解为左边的子问题: [3, 1] 和 右边子问题: []

其解等于: [3, 1] + [] * 1 * 5 * 1

发现,上面的解时错的。因为正向思考的情况下,以选择 1 为例,在点爆 1 气球后,两个左右子问题并不是独立的,所以这给计算子问题带来了障碍,怎么处理才能忽略中间的 1 呢?

逆向思考

[3, 1, 5] 为例,首先拿一个气球,把这个气球当做最后一个气球,然后点爆它。这样就能够将这个气球的左右两个子问题独立开。

换种方式来说,我们选这1这个气球,然后优先点爆左边和右边的气球之后,再最后点爆这个气嘴,这时可以看出左右两个子问题是独立的,他们只和1这个气球有关联。

定义状态转移方程

dp[i][j] i j 个气球(闭区间)能够获取的最大的硬币数量

dp[i][j] = dp[i][k - 1] + dp[k + 1][j] + nums[i - 1] * nums[k] * nums[j + 1] (i <= k <= j)

这种方式仍然是O(n!),但是由于利用了“记忆化”的特性,将重复的子问题写在了内存中,保证每一种子问题只计算一遍。这时能够通过,但是还可以优化。

代码

class Solution {
private:
    vector<vector<int>> dp;
    int helper(vector<int>& nums, int i, int j) {
        // boundary
        if (i > j) return 0;
        if (dp[i][j] > 0) return dp[i][j];
        
        // search
        for (int k = i; k <= j; ++k) {
            int left = helper(nums, i, k - 1);
            int right = helper(nums, k + 1, j);
            int delta = nums[k] * nums[i - 1] * nums[j + 1];
            dp[i][j] = max(dp[i][j], left + right + delta);
        }
        return dp[i][j];
    }
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        dp = vector<vector<int>>(n + 2, vector<int>(n + 2, 0));
        int ans = helper(nums, 1, n);
        return ans;
    }
};

解法三 动态规划——自底向上

自底向上,所有明确计算粒度:从 i j ,第一次长度是 1 ,第二次长度 2 ,直到长度是 n

第一层 循环定义长度 len from 1 to n

第二层 循环定义遍历的范围 i from 1 to n - len + 1 ,此时定义 j 的位置 j = i + len - 1

第三层 在当前情况下,选取 k 个气球,当做是最后一次点爆,一共有 k 种选择 (i <= k <= j) ,选取一个最大值。

返回 dp[1][n]

代码

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp = vector<vector<int>>(n + 2, vector<int>(n + 2, 0));
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        
        for (int len = 1; len <= n; ++len) {
            // i <= n - len (n - 1) + 1
            for (int i = 1; i <= n - len + 1; ++i) {
                int j = i + len - 1;
                for (int k = i; k <= j; ++k) {
                    dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + nums[k] * nums[i - 1] * nums[j + 1]);
                }
            }
        }
        
        return dp[1][n];
    }
};

参考

原题链接:https://leetcode.com/problems/burst-balloons/
笔记文档:https://docs.google.com/document/d/1FifQHUIEcpuU9R7OMOfKg0GGB1c8aRV6IGLyanKLXtk/edit?usp=sharing

本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/leetcode-312-burst-balloons/
最后修改日期:2020年6月18日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。