312. 戳气球
题目描述
有 n 个气球排成一排，编号为 0 到 n - 1，第 i 个气球上写着数字 nums[i]。
你需要把所有气球都戳破。戳破一个气球时，得到的硬币数等于它自己的数字乘以左右两侧相邻气球上的数字。这里的相邻指的是当前还没被戳破的气球；如果某一侧已经没有气球，就把那一侧当成数字为 1 的气球。
可以自由安排戳破的顺序。返回能得到的硬币总数的最大值。
示例 1
输入：nums = [3,1,5,8] 输出：167
解释：按 1、5、3、8 的顺序戳：3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167。
示例 2
输入：nums = [1,5] 输出：10
解释：先戳 1 得 1*1*5 = 5，再戳 5 得 1*5*1 = 5，共 10。
数据范围
n == nums.length1 <= n <= 3000 <= nums[i] <= 100
解题思路
正向想“先戳哪个”会改变邻居关系，难以分解。反过来想“最后戳哪个”：在两端补 1 得到 a，定义 dp[i][j] 为只戳破开区间 (i,j) 内所有气球的最大硬币。若 k 是区间内最后戳破的，那时它的邻居一定是 a[i] 和 a[j]，得到 a[i]*a[k]*a[j]，而左右两段 (i,k)、(k,j) 互不影响。按区间长度从小到大枚举。
为什么正确
计算 dp[i][j] 时，所有更短的区间 dp[i][k]、dp[k][j] 都已求好。
复杂度分析
时间 O(n^3)，空间 O(n^2)。
易错点
枚举的是“最后戳破”的气球而不是第一个；循环顺序必须按区间长度递增，否则会用到未计算的子区间。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxCoins(self, nums: List[int]) -> int:
a = [1] + nums + [1]
n = len(a)
dp = [[0] * n for _ in range(n)]
for length in range(2, n):
for i in range(n - length):
j = i + length
for k in range(i + 1, j):
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j])
return dp[0][n - 1]class Solution {
public int maxCoins(int[] nums) {
int[] a = new int[nums.length + 2]; a[0] = 1; a[nums.length + 1] = 1; for (int t = 0; t < nums.length; t++) a[t + 1] = nums[t];
int n = a.length;
int[][] dp = new int[n][n];
for (int length = 2; length < n; length++)
for (int i = 0; i < n - length; i++) {
int j = i + length;
for (int k = i + 1; k < j; k++)
dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
}
return dp[0][n - 1];
}
}class Solution {
public:
int maxCoins(vector<int>& nums) {
vector<int> a = {1}; a.insert(a.end(), nums.begin(), nums.end()); a.push_back(1);
int n = a.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int length = 2; length < n; length++)
for (int i = 0; i < n - length; i++) {
int j = i + length;
for (int k = i + 1; k < j; k++)
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
}
return dp[0][n - 1];
}
};func maxCoins(nums []int) int {
a := append(append([]int{1}, nums...), 1)
n := len(a)
dp := make([][]int, n)
for t := range dp {
dp[t] = make([]int, n)
}
for length := 2; length < n; length++ {
for i := 0; i < n-length; i++ {
j := i + length
for k := i + 1; k < j; k++ {
dp[i][j] = max(dp[i][j], dp[i][k]+dp[k][j]+a[i]*a[k]*a[j])
}
}
}
return dp[0][n-1]
}var maxCoins = function(nums) {
const a = [1, ...nums, 1];
const n = a.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let length = 2; length < n; length++)
for (let i = 0; i < n - length; i++) {
const j = i + length;
for (let k = i + 1; k < j; k++)
dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
}
return dp[0][n - 1];
};function maxCoins(nums: number[]): number {
const a = [1, ...nums, 1];
const n = a.length;
const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));
for (let length = 2; length < n; length++)
for (let i = 0; i < n - length; i++) {
const j = i + length;
for (let k = i + 1; k < j; k++)
dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
}
return dp[0][n - 1];
}