LeetCode(力扣) 312题：戳气球----动态规划求解附带详细注释_力扣戳气球

问题描述

有n个气球，编号为 0 到 n-1，每个气球上都标有一个数字，这些数字存在于数组nums中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得nums[i-1] * nums[i] * nums[i+1]枚硬币。这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

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

示例

输入：nums = [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

输入：nums = [1,5]
输出：10
1
2
3
4
5
6
7
8

思路分析

对于这种求解最值问题的题目，首选动态规划解法，动态规划yyds，哈哈哈哈。前边也说过用动态规划解决的问题，判断一个问题能不能用动态规划解决首先看该问题有没有最优子问题结构，找到最优子问题结构，其实就相当于定义了DP数组。在这个问题中，子问题可以定义为编号 i 到编号 j 的气球所能获得硬币的最大数量，那么DP数组定义为二维数组DP[ i ][ j ]。
在这个问题中，你戳爆一个气球，可以获得来自相邻两边气球的硬币奖励，但是那么多气球，我们也不知道先戳哪个才能得到最多的硬币奖励，那么干脆我们假设在编号 i 到 j 的气球中，其他气球都被戳烂了，只剩下了一个位于 k 位置的气球，我们假设最后一个戳烂
k 位置的气球获得的硬币奖励最多。即在编号 i 到 j 的气球中获得的硬币奖励总数DP[ i ][ j ] = DP[ i ][ k ] + nums[ i ] * nums[ k ] * nums[ j ]，这里其实类似于分治的思想，k 左边和右边分开计算。我们会问，i 和 j之间有那么多气球，我们怎么知道最后戳破哪一个获取的硬币最多呢，其实我们把所有情况列举出来，然后取最大值就可以了。
我们就从 (i,j) 开区间只有三个数字的时候开始计算，储存每个小区间可以得到金币的最大值，然后慢慢扩展到更大的区间，利用小区间里已经算好的数字来算更大的区间就可以啦 (这也是动态转移的优势，后边的结果被前边的结果影响，可通过前边的结果计算，从而避免重复计算量)！

代码

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # 先给nums数组扩展边界
        nums.insert(0, 1)
        nums.insert(len(nums), 1)
        # 创建DP数组
        DP = [[0] * len(nums) for i in range(len(nums))]

        # 寻找最后戳破哪一个气球得到的硬币奖励最多
        def select_last_ball(i, j):
            # 定义(i, j)区间获得的硬币数
            ij_coin = 0
            # 因为是(i, j)开区间，所以从 i + 1 开始, j - 1结束
            for k in range(i + 1, j):
                # 除K之外, 左右两边获取的硬币奖励
                left = DP[i][k]
                right = DP[k][j]
                # (i, j)区间气球获得硬币奖励为左边区间气球 + 右边区间气球 + 第K个气球(最后扎破), 戳破第K个气球是，就只剩[i, j]区间就只剩第i, j, k 3个气球了
                temp = left + nums[i]*nums[k]*nums[j] + right
                # 比较然后取最大值
                if temp > ij_coin:
                    ij_coin = temp
            DP[i][j] = ij_coin

        #对每一个区间长度进行循环, n为[i, j]区间的长度
        for n in range(2,len(nums)): #因为区间内至少要有三个气球, 所以从最小长度3开始，所以n从2开始
            #开区间长度会从3一直到len(nums)
            #因为这里取的是range，所以最后一个数字是len(nums)-1
            #对于每一个区间长度，循环区间开头的i
            for i in range(0,len(nums)-n): #i+n = len(nums)-1

                #计算这个区间的最多金币
                select_last_ball(i,i+n)
        # 返回编号区间为[0, len(nums)]内的气球, 即题目所给的所有气球
        return DP[0][len(nums)-1]      
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

运行结果

总结

个人感觉这道题很难，集合了动态规划和分治，它的DP数组定义很难找到 (我个人感觉哈)，也比较难考虑到，假设所有的气球都戳破，只剩边界两个气球和中间一个气球的想法，这是解这道题的关键。多多联系~欢迎大家一起学习交流。

参考

https://leetcode-cn.com/problems/burst-balloons/solution/zhe-ge-cai-pu-zi-ji-zai-jia-ye-neng-zuo-guan-jian-/