戳气球 | echo

312. 戳气球

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明:

你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:

输入: [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

为了避免讨论边界情况，我们将 nums 数组首尾各加上一个数字 1 ，将这个新数组叫做 val。

方法一：记忆化搜索

戳气球这个操作会使两个气球从不相邻变为相邻，使得后续操作难以进行，我们倒过来看这些操作，将全过程看作是每次添加一个气球。

定义方法 solve，令 solve(i, j)表示开区间(i, j)内位置全部填满能够得到的最多硬币数。由于是开区间，因此区间两端的气球编号就是 i 和 j，对应 val[i] 和 val[j]。

当 i >= j - 1 时，开区间中没有气球，solve(i, j)的值为 0 。
当i < j - 1 时，我们枚举开区间(i, j)内的全部位置 mid，令 mid 为当前区间第一个添加的气球，此时，区间中只有三个值 val[i]，val[mid]，val[j]，能得到的硬币数为这三个值的积。mid 将开区间(i, j)分为(i, mid)和(mid, j)两部分，我们递归地计算这两个部分对 solve(i, j)的贡献。

$$
solve(i, j) = \max^{j-1}_{mid=i+1}{val[i]\times val[mid]\times val[j] + solve(i,mid) + solve(mid,j) }\ \ {i < j - 1}
$$

$$
solve(i, j) = 0 \ \ {i \geq j - 1}
$$

为了避免重复计算，我们储存 solve 的结果。

class Solution {
    private int[][] rec;
    private int[] val;

    public int maxCoins(int[] nums) {
        int n = nums.length;
        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 + 2; i++){
            Arrays.fill(rec[i], -1);
        }

        return solve(0, n + 1);
    }

    public int solve(int left, int right){
        if(left >= right - 1){
            return 0;
        }
        if(rec[left][right] != -1){
            return rec[left][right];
        }

        for(int i = left + 1; i < right; i++){
            int sum = val[left] * val[i] * val[right];
            sum += solve(left, i) + solve(i, right);
            rec[left][right] = Math.max(rec[left][right], sum);
        }
        return rec[left][right];
    }
}

时间复杂度O(n^3)，空间复杂度O(n^2)。

方法二：动态规划

我们可以将自顶向下的记忆化搜索变为自底向上的动态规划，令 dp[i][j]表示填满开区间(i, j)能得到的最多硬币数，边界条件为 i >= j - 1，此时dp[i][j] = 0。
$$
dp[i][j]=\max^{j-1}_{k=i+1}{val[i]\times val[k]\times val[j] + solve(i,k) + solve(k,j) }\ \ {i < j - 1}
$$
$$
dp[i][j] = 0 \ \ {i \geq j - 1}
$$

最终答案为dp[0][n + 1]。

class Solution {
    
    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--){//枚举左边界
            for(int j = i + 2; j <= n + 1; j++){//枚举右边界
                for(int k = i + 1; k < j; k++){//枚举开区间(i, j)中的全部位置
                    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];
    }
}

时间复杂度O(n^3)，空间复杂度O(n^2)。