描述
有 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 = 315 + 358 + 138 + 181 = 167
示例 2：
输入：nums = [1,5]
输出：10
思路
不要想先戳哪个，想最后戳的是哪个。
或者这个场景可以等效为逆序场景：向槽位中添加气球，添加一个就加一次分数。
想法过于精妙，看代码懂的都懂。
启发：一开始自己总想着进行某些数学证明，看来做编程题最好还是不要往这方向去钻
代码
不多说直接看懂
class Solution:def maxCoins(self, nums: List[int]) -> int:n=len(nums)self.nums = [1]+nums+[1]return self.dfs(1,n)@cachedef dfs(self,i,j):if i>j:return 0return max( self.dfs(i,k-1)+self.dfs(k+1,j)+self.nums[i-1]*self.nums[k]*self.nums[j+1]for k in range(i,j+1))
