题目链接：https://leetcode.cn/problems/burst-balloons/
难度：困难

描述：
有 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. class Solution:
  2.     def maxCoins(self, nums: List[int]) -> int:
  3.         nums.insert(0, 1)
  4.         nums.insert(len(nums), 1)
  6.         # r[i][j]代表区间(i, j)中能获得的最大硬币数量
  7.         r = [[0] * len(nums) for _ in range(len(nums))]
  9.         for length in range(2, len(nums)):
  10.             for i in range(len(nums) - length):
  11.                 j = i + length
  12.                 # k是最后一个被戳破的气球
  13.                 for k in range(i+1, j):
  14.                     r[i][j] = max(r[i][j], r[i][k] + r[k][j] + nums[i] * nums[k] * nums[j])
  16.         return r[0][len(nums)-1]