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] 的值，这是我们戳破所有气球后能得到的最大分数。
