312 - Burst Balloons

题目介绍

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:167Explanation: 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

翻译

有 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

解题思路

        首先，第一个思路是暴力求解，枚举出所有可能的排列可能，然后算分数，并取最大值。但是，显然，我们会有n!中可能的排列，时间复杂度太大，因而放弃它。

        之后，我在想，能否将原问题分解成子问题，递归求解。以【3,1,5,8】为例，因为，踩气球是一个一个地踩，我可以做的一个行为是任踩一个气球，计算目前所得分数，并加上剩余气球能够得到的分数，由于，我有多种选择的可能性，那么，我就计算所有的可能，并选取得分最高的方案。如，【3,1,5,8】 可有四种方案，3*1 + 【1,5,8】，3*1*5 +【3,5,8】，1*5*8 +【3,1,8】和 5*8 + 【3,1,5】。倘若递归的数列长度等于3，那么，我们就枚举出3！= 6种可能性，然后选择最大的分数返回。同时每当计算出一组序列的得分时，就把它存在一个字典dic里, 如dic[(5,8)] = 48，当需要求的序列的分数已经存在与dic中式，直接将其求出。但是，这种递归的时间复杂度也很高。之后，我在想，现在复杂度高的原因，是对于每一个长度为m的序列，我都要枚举出m种可能，那么迭代后复杂度必然高，那么，会不会存在一种规律使得我可以不每次都枚举m种可能，而是，最有结果出现在有限的几种可能中呢？于是，我做出了几个猜想，1. 每次先踩分数最小的（失败，反例【1,2,100,1】）2. 每次先踩其相邻两个数之积最大的数（失败，反例【9,76,64,21,97,60,5】）。

        由于没有找到一种可以降低枚举可能次数的策略，所以，我将思路放在DP上，因为，有一个很明显的直觉，就是倘若知道任意一个子段可以取得的最大分数，那么，我就可以求得整个子段的最大分数。既然决定了使用DP，那么之后我就开始着手重新定义原问题。

        首先，我思考，能否将一个长度为n的数列 l 看成是为 l[0:-1] 和 l[-1],两部分，那么，倘若我知道了前一部分的最大分数，那么我只需要再让它加上踩破最后一个的分数，如【3,1,5,8】可分为【3,1,5】和【8】，那么最大的分数是score（【3,1,5】）+ 8*5，然后从0到n-1依次递归。但这样显然书错误的，因为，这样定义问题实际上是附加了一个隐含条件，即，一定要先踩最后一个气球，再踩前面的气球，这显然与原问题不符。

        虽然，上面的假设是错误的，但是，却给了我一个思路，如何将上面假设做适当修改，使他符合原题呢？经过思考，我觉得，问题的关键在于 -- 每次踩的气球都是随机的。既然每次踩的气球的是随机的，那么，我就先假设踩的气球是第m个（假设数列为nums,长度为L，m<L）。在我踩了第m个气球后，造成的结果是什么？那就是，原数列变成了两部分，nums[:m]和num[m+1:L-1],同时，由于这一脚，我获得了nums[m-1]*nums[m]*nums[m+1]分

        原本以后我将问题这样转化后在DP就可以通过了，然而结果却显示了错误。我又进行了分析，结果发现了一个问题，倘若我踩了第k个气球，那么当踩第k-1个气球时，会发生什么情况呢？会发生计算它的分数时，它的右侧是没有球的！！这显然不合理，因为踩了第k个气球后，它后面会接在第k-1个气球后。 那么，我想着能不能把第在计算第k-1个气球得分时，将它的右侧气球强制定义为第k+1个气球。粗想一下感觉可行，但是，仔细一想就发现了问题，倘若第k+1气球在第k-1个气球之前被踩爆了，怎么办？ 这个问题会越来越复杂，最重要的是被分割成两半的nums[:m]和num[m+1:L-1]和变得彼此不独立，而这对DP来说是难以接受的。

        紧接着，我的问题就变成了，如何使被切分的两部分变得彼此独立。经过思考，我发现，这两部分的独立与否，取决与nums[k-1]的右侧气球是谁和nums[k+1]的左侧气球是谁。当第k个气球被踩爆了，那么nums[k-1]的右侧气球和nums[k+1]的左侧气球就会发生变化.....(ーー゛)，那我不睬第k个气球了！！！那么，我就可以保证nums[k-1]的右侧气球和nums[k+1]的左侧气球都不会变化，因为都是第k个气球，然而，我不可能不猜它呀！！！思考后，我意识到，我只要在nums[:m]和num[m+1:L-1]都被踩爆后再踩第k个气球，那么就可以达到我隔离两边的目的了。

        现在，还剩一步，就是计算踩爆第k个气球的得分，当k是原问题最后一个被踩爆的气球时，可增加分数nums[k]，即它本身，然而，这个规律却不适合与其子问题，如原问题是【1,2,3,4,5,6,7,8】，【4,5,6】是它的一个子问题，假如5所代表的气球是子问题中最后被踩爆的，那么它的得分显然不是5，因为她并不是全局最后一个被踩爆的，它周围必要还有其他气球。然而它左右的气球会存在与其他的子问题中，并且是变化的，这是不能接受的。于是，我想着怎么把最后一个踩爆的气球左右的气球固定住。于是就假设序列的最左端和最右段气球被最后踩爆，而第k个气球是在非最左和非最右气球外被最后踩爆的，那么第k个气球的分数就固定了，即 最左的分数×本身的分数×最右的分数。

        之后，在回顾一遍原问题的第k个气球被最后踩爆，那么，它的得分就是最左的分数×本身的分数×最右的分数，这显然不对，因为，这相当于隐性的规定原问题最左边和最右边的气球被最后踩爆。这时候有两种方式，一种是强行指定，在第一次从原问题处理分离子问题时，分数之加这个气球本身的分数，其他情况则加 最左的分数×本身的分数×最右的分数。另一种方法就是在原问题分数序列左右都加上1，这样既不影响最终分数，又避免了第一次分离子问题时出现的例外情况。        

        至此，我们所做的只是计算出最后踩爆第k个气球的得分，而题目要求的是踩爆气球的最大得分，因此，我们可以遍历所有的，并取其中得分最大的作为答案。

        以上，是我做题时的思考，下面，再总结一下要点：

        1. 重新定义问题：计算任意一个气球被最后踩爆时的最大得分，并分返回其中的最大值。

        2. 使用动态规划处理这个问题，将原问题分为nums[0:k] 和 num[k:L-1]两部分，并获得加分 nums[0]*nums[k]*nums[1]

        3. 遍历所有的k，从中取得得分最多的方案。

        4. 在原数列两边加边框1，以匹配第一次分离子问题的情况。

        代码：

        https://github.com/guiguiJY/Leetcode/blob/master/312.py