力扣每日一题 6/9

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 的气球。

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

示例 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

示例 2：

输入：nums = [1,5]
输出：10

提示：

• n == nums.length
• 1 <= n <= 300
• 0 <= nums[i] <= 100

 题目分析：

        这道题需要用到数组和动态规划来解，数组用来储存遍历到的金币值，动态规划遍历最后一个被戳破的气球的下标，然后将其分为左右和自身两部分，计算出金币值与当前最大的金币值做比较。遍历完即可。

代码实现：

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        #nums首尾添加1，方便处理边界情况
        nums=[1]+nums+[1]
        dp = [[0]*(len(nums)) for i in range(len(nums))]
        def calc(i,j):
            m = 0 
            #k是(i,j)区间内最后一个被戳的气球
            for k in range(i+1,j): #k取值在(i,j)开区间中
                #以下都是开区间(i,k), (k,j)
                l = dp[i][k]
                r = dp[k][j]
                key = l+r+ nums[i]*nums[k]*nums[j]
                if key > m: m = key
            dp[i][j] = m  # 存储到dp中

        #对每一个区间长度进行循环
        for n in range(2,len(nums)): #区间长度的初始位置
            #开区间长度会从3一直到len(nums)
            #对于每一个区间长度，循环区间开头的i
            for i in range(0,len(nums)-n): #i+n = len(nums)-1
                calc(i,i+n)
        return dp[0][len(nums)-1]

总结： 

        这道题考到了动态规划，但是动态规划是我的弱项，对于解出这道题来说还是远远不够的，所以又看了题解才磨出来了这道题。这个动态规划的解决方案的关键在于，我们通过递归地计算每个子问题的最优解，来构建整个问题的最优解。每次我们选择一个气球作为最后一个被戳破的气球，并将其乘积加到最优解上，然后递归地计算左右两边的子区间。通过这种方法，我们能够得到全局的最优解。

        我们定义了一个二维数组 dp，其中 dp[i][j] 表示在戳破气球 i 和 j 之间的所有气球（包括 i 和 j）后我们能得到的最大分数。注意这里的 i 和 j 指的是气球的下标，dp 数组的大小为 len(nums) x len(nums)。

  calc 函数的作用是计算从 i 到 j 的区间内的最大分数，并将其存储在 dp[i][j] 中。函数内部通过遍历 (i+1, j) 区间内的所有可能的 k，来找到最后一个被戳破的气球 k。对于每个 k，我们计算 dp[i][k] 和 dp[k][j] 的和，再加上气球 i、k 和 j 的分数乘积，然后更新 dp[i][j] 的最大值。

       最后，我们通过循环不同长度的区间来填充 dp 数组。对于每个区间长度 n，我们从区间开头 i 开始，计算区间 (i, i+n) 的最大分数。通过这种方式，我们最终得到了 dp[0][len(nums)-1] 的值，这是我们戳破所有气球后能得到的最大分数。