LeetCode：312. Burst Balloons - Python_有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums

问题描述：

312. 戳气球

有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

示例:

输入: [3,1,5,8]
输出: 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

问题分析：

其实一开始用的是贪心算法，但是提交一直没对，后来去讨论区看看了一下，学习了半天才知道是动态规划题目。
（1）先理解一个事情，就是把整个数列看做一个整体，那么最优解值，一定是最后一个气球i值（i 是未知的），加上以i 为分界线，左右两个区间的最优解（有点像二分法）。不难理解，最后就剩下一个气球时，很显然，把两边的最优解加上最后一个气球值，就是整体的最优解。

（2）问题：最后被戳破的气球i是哪一个？因为已经知道区间内的所有数字，那么就可以枚举这些数字，找到最优的那个i 。这类问题一般归为区间 dp 。

（3）问题：左右小区间的最优解如何确定？那么现在就是，从最小区间开始计算，通俗的讲，先计算长度2的小区间，然后依次增加区间的长度。每次计算时，小区间就像一个滑动窗口，例如从长度为2的小区间作为一个窗口，从左向右依次滑动，求出所有小区间的最优解保存到dp[l][r]中。
可以看出计算过程是自底向上的。所以dp[l][r]只用到了上三角的空间(l < r)。

（4）dp状态转换方程：

dp[left][right] = max(dp[left][right], nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right])
1

dp[left][right]，表示区间left-->right的最优解（不包括，left和right 两个边界）

nums[left] * nums[i] * nums[right]，表示最后一个被戳破的气球的得分，为什么要乘上两个边界值那？因为它是最后一个被戳破的气球，整体来看，最后就剩下一个，就是乘上两个1，在子区间内，就是乘上两边的边界值了。

max(dp[left][right], nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right])，表示从区间内开始枚举i，计算出本次区间的最优解。

Python3实现：

# @Time   :2018/6/22
# 解题思路 区间动态规划


class Solution:
    def maxCoins(self, iNums):
        nums = [1] + [i for i in iNums if i > 0] + [1]  # 清除为0的数字，因为0不会得分，然后首尾添加[1],方便计算
        n = len(nums)
        dp = [[0] * n for _ in range(n)]  # 初始化dp
        for k in range(2, n):  # k 确定一个滑动窗口的大小，从2开始
            for left in range(0, n - k):  # 滑动窗口，从左向右滑动，确定区间的开始（left）、结束（right）位置
                right = left + k
                for i in range(left + 1, right):  # 开始枚举，区间内哪一个数字作为最后一个被戳破，使其得分最高
                    dp[left][right] = max(dp[left][right], nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right])
        return dp[0][n - 1]


if __name__ == '__main__':
    nums = [3,1,5,8]
    solu = Solution()
    out = solu.maxCoins(nums)
    print(out)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

补充知识：

动态规划的两个基本条件：
（1）最优子结构：每个区间都符合这样解的结构。
（2）重叠子问题：例如上题中，左右区间又生成左右区间，构成重叠问题。

声明：如有不妥或问题还请您，批评指正，自己只是学习总结，不涉及其他，大神勿喷哦。

（这个题目其实是，去年阿里的测验题，总结过一次，有一次百度阿里的题目，发现这个被举报了？无语，还是涉嫌广告、政治，大神勿喷 ，菜鸟只是想总结之前的学习的过程，方便以后的复习，有问题可以留言指正哦）