312. 戳气球
有 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 <= 5000 <= nums[i] <= 100
解题思路
方法一：递归 + 记忆化搜索
我们观察戳气球的操作，发现这会导致两个气球从不相邻变成相邻，使得后续操作难以处理。
于是我们倒过来看这些操作，将全过程看作是每次添加一个气球。
要在(i, j)区间填满气球的最大的收益是, 首先枚举(i, j)中所有的位置K, 在K处填充一个气球, 得到一个收益nums[i] * nums[j] * nums[k]。然后将(i, j)分成了2部分, 分别是(i, k)和(k, j)。递归的计算这两部分的收益, 然后相加即可。
为了统一边界的处理, 可以在数组的这两个边界分别加上元素1
时间复杂度：O(n^3)，其中 n 是气球数量。区间数为 n^2，区间迭代复杂度为 O(n)，最终复杂度为 O(n^2 * n) = O(n^3)
空间复杂度：O(n^2)，其中 n 是气球数量。缓存大小为区间的个数。
public int[][] rec;
public int[] val;
public int maxCoins(int[] nums) {
int n = nums.length;
// 填充两侧边界为1
val = new int[n + 2];
for (int i = 1; i <= n; i++) {
val[i] = nums[i - 1];
}
val[0] = val[n + 1] = 1;
// 初始化记忆化数组
rec = new int[n + 2][n + 2];
for (int i = 0; i <= n + 1; i++) {
Arrays.fill(rec[i], -1);
}
// 递归[0, n-1]部分
return solve(0, n + 1);
}
public int solve(int left, int right) {
// (left, right) 中间没有可供填充的部分
if (left >= right - 1) {
return 0;
}
// 返回之前存储过的中间结果
if (rec[left][right] != -1) {
return rec[left][right];
}
// 遍历(left, right)中间的所有的位置
for (int i = left + 1; i < right; i++) {
// 填充第i个位置所获得的收益
int sum = val[left] * val[i] * val[right];
// 将(left, right) 分成 (left, i) 和 (i, right)两部分
// 递归得计算这两部分, 得到把(left, right)这两个位置填充满的收益
sum += solve(left, i) + solve(i, right);
// 更新枚举(left, right) 所有位置的产生收益的最大值
rec[left][right] = Math.max(rec[left][right], sum);
}
return rec[left][right];
}
方法二： 动态规划(迭代)
动态规划的迭代版本和上面的递归版本思路是差不多的。不过迭代的过程是从后往前迭代。
设置矩阵rec[][]表示填充(i, j)的所有元素的收益。
那么在(i, j)相等或者相邻的情况下, 收益是为0的。
迭代的方式是第一个for循环 i, 从后往前迭代, 第二个for循环 j, 从i出开始往后迭代。在第三个for循环从前往后枚举(i, j)间的每一个位置。
public int maxCoins(int[] nums) {
int n = nums.length;
int[][] rec = new int[n + 2][n + 2];
int[] val = new int[n + 2];
val[0] = val[n + 1] = 1;
for (int i = 1; i <= n; i++) {
val[i] = nums[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
// j从i+2 开始 让(i, j)恰好有一个中间的空位
for (int j = i + 2; j <= n + 1; j++) {
// 尝试 (i, j)之间的所有位置, 找到一个填满 i, j 的最大值
for (int k = i + 1; k < j; k++) {
int sum = val[i] * val[k] * val[j];
sum += rec[i][k] + rec[k][j];
rec[i][j] = Math.max(rec[i][j], sum);
}
}
}
return rec[0][n + 1];
}
当然这道题可以换一种迭代的方式, i的迭代方式是从前向后迭代, 第二个for循环j, 从i开始从后往前迭代。第三个for循环从前往后枚举(i, j)的每一个位置。
public int maxCoins(int[] nums) {
int n = nums.length;
int[][] rec = new int[n + 2][n + 2];
int[] val = new int[n + 2];
val[0] = val[n + 1] = 1;
for (int i = 1; i <= n; i++) {
val[i] = nums[i - 1];
}
for (int i = 2; i <= n + 1; i++) {
for (int j = i - 2; j >= 0; j--) {
for (int k = j + 1; k < i; k++) {
int sum = val[j] * val[k] * val[i];
sum += rec[j][k] + rec[k][i];
rec[j][i] = Math.max(rec[j][i], sum);
}
}
}
return rec[0][n + 1];
}