Leetcode Link: 312. 戳气球 - 力扣（LeetCode）
题目
有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
解法一
思路：回溯暴搜
非常naive的想法，回溯的时候注意pop掉当前考虑的位置，并且在回溯函数执行完后要insert回来。
题解：超时严重，长度为10的时候就超时了。
class Solution:
def maxCoins(self, nums: List[int]) -> int:
def process():
if len(nums) == 0:
return 0
res = 1
for i in range(len(nums)):
val = nums[i]
tmp = nums[i]
if i-1>=0:
tmp *= nums[i-1]
if i+1 <= len(nums)-1:
tmp *= nums[i+1]
nums.pop(i)
res = max(res, tmp+process())
nums.insert(i, val)
return res
return process()解法二
思路： 从暴力递归到动态规划
先想想这题思考起来为啥感觉很拧巴?
假设我们就正常思考这个问题，我们找了一个 k 位置的气球扎了，结果发现，k-1 和 k+1 相邻了，也就是说每个位置的气球随着我们扎得位置不一样，他的相邻位置会变，就是这个变化让我们无法用一个很自然、很朴素的想法去模拟，所以实现起来会很拧巴。
既然正向不行，那我们索性反着来，只思考我们最后扎哪个气球。 可以预知的是，不考虑实现过程，反过来计算的结果和正着计算结果是一样的（可以举个例子，然后正反计算一下）。
在此之前，我们先在 nums 的前后各添加 1 来防止越界同时可以减少判断，避免逻辑不一致。
nums.insert(0, 1)
nums.append(1)我们考虑在 (l, r) 的开区间上最后扎哪一个气球，这里假设扎的是 k 位置的气球 (l < k < r)，易知此时 res = num[l]*nums[k]*nums[r]，即”最后一扎”得到的硬币数。
此时，k 将 (l, r) 分割成了两部分，即 (l, k) 和 (k, r)，由于 k 位置的气球我们已经给扎了，所以上面分割出来的两个区间都是开区间。
接下来，问题就变成了，在 (l, k) 和 (k, r) 两个开区间中，我们分别”最后扎的”是哪一个，这样就分成了两个子问题。
实际上这里我们并不会关心在这两个区间里究竟哪个是先扎的，我们只是将问题分解成了两个独立的子问题。
这样，我们就完成了问题的分解，可以用暴力递归的方式解决了
题解：
class Solution:
def maxCoins(self, nums: List[int]) -> int:
nums.append(1) # 结尾添0
nums.insert(0, 1) # 开始添0
@cache
def process(l, r):
if l == r-1: # base: 左右边界相邻，实际上相当于没有可以被扎的气球了
return 0
if l == r-2: # base: 左右边界差2，实际上只有中间一个可以扎的气球了
return nums[l]*nums[r-1]*nums[r]
res = -float('inf') # 提前定义一个最小的答案
# 寻找在(l, r)开区间内最后一个扎的气球，注意不能取到边界上
for k in range(l+1, r):
res = max(res, nums[k]*nums[l]*nums[r]+process(l, k)+process(k, r))
return res
return process(0, len(nums)-1)复习时错了，两个base case思考错误。务必注意只有两个球的时候，结果为0。而第二个base case可以不写，在循环体里会计算得到。
解法三
思路：解法二改写动态规划
dp 五步走：
- 确定
dp[l][r]内容：记录(l, r)开区间的最大硬币数 - 递推公式：见暴力递归
- 初始化：
if l == r-1: dp[l][r]=0和if l == r-2: dp[l][r]=nums[l]*nums[l+1]*nums[r] - 遍历顺序：这个不好直接看出来，看下图吧，结论是行 (
l) 逆序，列 (r) 正序 - 举例子
通过上图我们易知，顺序就是行倒序，列正序
题解：
class Solution:
def maxCoins(self, nums: List[int]) -> int:
nums.append(1) # 结尾添0
nums.insert(0, 1) # 开始添0
# dp[l][r]
dp = [[0 for _ in range(len(nums))] for _ in range(len(nums))]
# 初始化，其实有两个，=0的那个可以省略
for i in range(len(nums)-2):
dp[i][i+2] = nums[i]*nums[i+1]*nums[i+2]
for l in range(len(nums)-1, -1, -1): # 必需反着来
for r in range(l+3, len(nums)): # l+1, l+2 都已经初始化了
res = -float('inf')
for k in range(l+1, r):
res = max(res, nums[k]*nums[l]*nums[r]+dp[l][k]+dp[k][r])
dp[l][r] = res
return dp[0][len(nums)-1]