难度: Hard
有 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.length1 <= n <= 3000 <= nums[i] <= 100运行时间: 1095 ms
内存: 17.9 MB
class Solution:
def maxCoins(self, nums: List[int]) -> int:
n = len(nums)
nums += [1, 1]
dp = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(n - 2, -2, -1):
for j in range(i + 2, n + 1):
numsij = nums[i] * nums[j]
dpij = 0
for k in range(i + 1, j):
ikj = dp[i][k] + dp[k][j] + numsij * nums[k]
if ikj > dpij:
dpij = ikj
dp[i][j] = dpij
return dp[-1][n]
这个题解使用动态规划来解决戳气球问题。主要思路是：考虑最后戳破的气球是哪个，假设是第 k 个气球，那么状态转移方程就是 dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])，其中 dp[i][j] 表示戳破 (i, j) 范围内的所有气球能得到的最大硬币数，k 是 (i, j) 范围内最后一个戳破的气球。根据状态转移方程写出代码即可。
时间复杂度: O(n^3)
空间复杂度: O(n^2)
class Solution:
def maxCoins(self, nums: List[int]) -> int:
n = len(nums)
nums += [1, 1] # 在原数组左右各加一个1，简化边界条件判断
dp = [[0] * (n + 2) for _ in range(n + 2)] # 初始化dp数组
for i in range(n - 2, -2, -1): # 开区间(i, j)从下往上遍历
for j in range(i + 2, n + 1):
numsij = nums[i] * nums[j] # 提前计算 nums[i]*nums[j]，避免重复计算
dpij = 0
for k in range(i + 1, j): # k作为(i, j)范围内最后戳破的气球
ikj = dp[i][k] + dp[k][j] + numsij * nums[k] # 状态转移方程
if ikj > dpij:
dpij = ikj
dp[i][j] = dpij
return dp[-1][n]
选择动态规划方法是因为戳气球问题涉及到多个选择与决策的顺序，这些决策之间存在重叠的子问题，并且具有最优子结构特性。贪心算法虽然在某些步骤可能找到局部最优解，但它不能保证全局最优解，因为戳破一个气球的决策会影响后续的选择。回溯算法能够遍历所有可能的选择，但其时间复杂度通常非常高，不适合解决问题规模较大的情况。动态规划通过建立状态转移方程，逐步求解，避免了重复计算，因此在时间和空间效率上更优。
在动态规划过程中，确保所有情况都被考虑到的关键是通过妥善的循环结构来遍历所有可能的状态。对于每一对(i, j)，我们考虑所有可能的k（i < k < j），使得k是(i, j)区间内最后一个被戳破的气球。通过从较小的子区间开始计算，逐步扩展到更大的子区间，我们可以确保在计算dp[i][j]时，dp[i][k]和dp[k][j]已经被计算过，从而保证了计算的正确性和完整性。
是的，dp数组初始化为0的确是因为在任何开始(i)和结束(j)位置之间，如果没有气球存在（即i直接连接到j，中间没有k可以选择），那么该区间能够获得的硬币数自然为0。这种初始化方式简化了边界条件的处理，并且符合问题的逻辑，即没有气球可以戳破时，收益为零。
加入两个值为1的气球是为了简化边界条件处理，这些边界气球不会影响最终计算的结果。加入这些气球后，我们可以假设所有的戳气球操作都是在一个完整的框架内执行的，即每个子问题的边界都有气球存在。这样可以避免在实现时对边界情况进行特殊处理，简化代码逻辑。实际上，这些边界气球的戳破只会在最初和最后发生，且它们的值设为1，所以对于计算其他气球带来的硬币总数没有直接影响。