LeetCode 312. 戳气球
数组 nums 中，保存了每个气球上的数字，戳破一个气球，得分是nums[i - 1] * nums[i] * nums[i + 1]（若越界，认为两个边界上有数值为1的虚拟气球）
可以按照不同顺序戳破气球，问所能得到的最高分数
如nums = [3,1,5,8]，返回167（[3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []）
暴力解法：回溯
涉及求最值，一定要穷举所有可能结果，然后比较得出最值
暴力穷举就是回溯，若能找到独立子问题，更聪明的穷举就是动态规划
回溯思路：穷举戳破气球的所有不同顺序，这就相当于“全排列”问题，用数组代表气球，并动态更新数组的值，从而实时模拟气球的情况，注意每次做选择后还原现场
class Solution:
def maxCoins(self, nums: List[int]) -> int:
maxScore = 0
def backtrack(arr, score):
# arr保存当前气球的情况
nonlocal maxScore
if not arr:# 戳完了所有气球
maxScore = max(maxScore, score)
return
for i in range(len(arr)):
l = 1 if i == 0 else arr[i - 1]
r = 1 if i == len(arr) - 1 else arr[i + 1]
point = l * r * arr[i]
# 尝试戳第i个气球
balloon = arr.pop(i)
backtrack(arr, score + point)
# 还原现场
arr.insert(i, balloon)
backtrack(nums, 0)
return maxScore
动态规划
思路：
- 动态规划要求子问题独立，因此我们需要转化dp的定义，构造独立的子问题
- 怎样找互不关联的子问题呢？
可以利用逆向思维求解：对所有气球，考虑最后戳破哪一个气球得分最高
如果最后戳破气球i，又构造出了两个独立子问题：对于气球i左边的那些气球，最后戳破哪个分最高/对于气球i右边的那些气球，最后戳破哪个分最高
- 状态：当前考虑的这些气球的左右边界
选择：对于这些气球，最后戳破哪一个，总得分最高 - 为了代码统一，先将左右两侧的“虚拟气球”加到数组中
数组nums的下标范围变为0~(L=n+1)(n为原来的总气球数量) - dp数组定义：dp[i][j]表示戳破区间
(i,j)内（不包括i、j）的气球的最高分，则我们要求的答案就是dp[0][L-1]
每次尝试不同的气球作为最后戳破的气球（同时分出两个子问题dp[0][i]和dp[i][L-1]），并求最大值 - 状态转移方程：
假设最后戳破了气球k，那么dp[i][j]=max(dp[i][j],nums[i]*nums[k]*nums[j]+dp[i][k]+dp[k][j])
理解：对于区间(i,j)，最后戳破气球k时，其两边一定是气球i和j
实现:
根据base case和答案位置dp[0][L-1]可知，求解顺序从下往上从左往右
i从L-3开始，j从i+2开始，k从i+1开始
class Solution:
def maxCoins(self, nums: List[int]) -> int:
# 首尾加上“虚拟气球”,之后注意气球0/气球n+1不可戳破
nums.insert(0, 1)
nums.append(1)
# 气球总数
L = len(nums) # 总气球数，气球0/气球L-1不可戳破
# dp[i][j]表示戳破区间(i,j)内（不包括i、j）的气球的最高分，则我们要求的答案就是dp[0][L-1]
dp = [[0 for _ in range(L)] for _ in range(L)]
# base case :i>=j时/j==i+1时，没有气球可以戳破，得分0
for i in range(L - 3, -1, -1):
for j in range(i + 2, L):
for k in range(i + 1, j):
# 对于区间(i,j)内的气球，最后戳破气球k
# 得分=最后戳破气球得分+左区间得分+右区间得分
dp[i][j] = max(dp[i][j], nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j])
return dp[0][L - 1]