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.length
• 1 <= n <= 500
• 0 <= 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];
}