leetcode 312. Burst Balloons

pinecone 发布于2019-08-15 14:49 / 552人阅读

摘要：之后该气球将消失，从而其左右两个气球成为相邻的气球。这意味着的时间复杂度。这样就违背了分治法将问题分解为独立问题的要求。此时得到的子队列长度等于，因此将无法拆解，即结束。

题目要求

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: 
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

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

这里讲了一个炸气球小游戏的规则。当我们选中一个气球并炸掉它后，会得到该气球以及其相邻两个气球的分数的乘积，并加入我们的积分。之后该气球将消失，从而其左右两个气球成为相邻的气球。问如何选择气球才能使得积分数最高。

思路和代码

我直接解释一下看到的最高票的回答。

如果采用暴力法的话，我们会遍历出所有可能的结果，并且比较其最终获得最高积分值。这意味着O(n!)的时间复杂度。

如果采用动态规划法的话，我们在知道了炸掉k个气球之后的最大积分，然后计算炸掉k+1个气球的最大积分。时间依旧感人。

这里采用的是backtracking+分治法来解决。当我们正向思考这道题时，我们可能会想，随机选择一个气球，按该气球作为分界线分为两个子气球队列。这时再分别计算左右两个队列可以得到的最大积分。
但是这里有一个问题在于，左边队列炸掉气球的顺序可能会影响到右边气球的顺序，比如假设存在这样一列气球对应的积分为3，2，4，1，5,我们取4作为分界点，分为两个子数组3,2,1,5那么如果左边气球炸掉的顺序为2,3，则右边队列的最左侧值则会先是2，再是3。这样就违背了分治法将问题分解为独立问题的要求。因此这种思路无法解决该问题。

但是如果反过来思考，假设我们先选取最后一个炸掉的气球，那么我们知道这个获得的积分一定是nums[i]*nums[left]*nums[right]，则以该气球作为分界点将队列分解后获得的两个子队列的边界是一定的。举个例子3,2,4,1,5：
首先，我们将其填充为1,3,2,4,1,5,1
然后我们将队列从2分解开来，即2是最后一个炸掉的气球，那么该气球的积分数为1*2*1
自队列分别为1,3,2和2,4,1,5,1。
那么假设我们再拆解1,3,2中的3，则结果为1*3*2。此时得到的子队列长度等于2，因此将无法拆解，即结束。

    public int maxCoins(int[] nums) {
        int[] modifiedNums = new int[nums.length + 2];
        int n = 1;
        for(int num : nums){modifiedNums[n++] = num;}
        modifiedNums[0] = modifiedNums[n++] = 1;
        
        int[][] memo = new int[n][n];
        return maxCoins(modifiedNums, 0, n-1, memo);
    }
    
    public int maxCoins(int[] nums, int left, int right, int[][] memo){
        if(left+1 >=right) return 0;
        if(memo[left][right] != 0) return memo[left][right];
        int res = 0;
        for(int i = left+1; i

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 Burst Balloons Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68842.html

[LeetCode] 312. Burst Balloons

Problem 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...

TerryCai 2019-08-16 13:53 评论0 收藏0
312. Burst Balloons

摘要：接下来就是方程的问题了。首先肯定是要遍历切分点，然后找使最大的切分点，容易想到这个切分点表示的是扎破气球的位置。还有一种考虑的方式，就是说和不算在内。那么方程现在变成，并且取不到边界或者。 312. Burst Balloons 题目链接：https://leetcode.com/problems... 这题的dp方程还是挺难想的。首先subproblem比较容易：dp[i][j]: ...

calx 2019-08-19 10:45 评论0 收藏0
312. Burst Balloons

public class Solution { public int maxCoins(int[] nums) { int n = nums.length; int[] newNum = new int[n+2]; newNum[0] = 1; newNum[n+1] = 1; for(int i=0; i

wyk1184 2019-08-16 10:36 评论0 收藏0
[Leetcode] Permutation Sequence 全排列序列

摘要：找规律复杂度时间空间思路由于我们只要得到第个全排列，而不是所有全排列，我们不一定要将所有可能都搜索一遍。根据全排列顺序的性质，我们可以总结出一个规律假设全排列有个数组成，则第个全排列的第一位是。然后将得到，这个就是下一轮的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

testHs 2019-08-14 12:34 评论0 收藏0
力扣(LeetCode)756

摘要：题目地址题目描述给出集合，其所有元素共有种排列。说明给定的范围是。第二种是回溯法求全排列，设置一个全局变量为当前求出的排列数，求出第个全排列，也就是时，停止所有递归否则会超时。题目地址：https://leetcode-cn.com/probl...题目描述：给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时,...

Keven 2019-08-16 15:17 评论0 收藏0