LeetCode.312.Burst Balloons 戳气球

题目描述

312 Burst Balloons
https://leetcode-cn.com/problems/burst-balloons/

有 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，构成长度为 nums.length + 2 的数组 nums2

设 dp[i][j] 表示开区间 (i,j) 能得到的最大金币数
则 dp[i][j] = max_{i<k<j}{dp[i][k] + dp[k][j] + nums2[i] * nums2[k] * nums2[j]}
即 在开区间 (i,j) 中找一个下标 k，表示最后被戳破的气球下标，k 的取值为 [i+1, j-1], 遍历 k 所有可能的取值，求出使得 dp[i][j] 值最大的。
对于每个 k 值，我们已经假设最后戳破 k，所以 dp[i][j] 的值就等于开区间 (i,k) 可获得的最大金币数 + 开区间 (k,j) 可获得的最大金币数 + 最后戳破 k 可获得的金币数 nums2[i] * nums2[k] * nums2[j]
dp[0][nums2.length - 1] 就是最终结果。

注意：动态规划中遍历填表时，必须保证当前计算所依赖的中间结果已经计算好，由于 dp[i][j] 依赖于 dp[k][j] 而 k > i，即第 i 行的结果依赖行数大于 i 的结果，所以要 i 要从 nums2.length-1 开始递减遍历。

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

private static class SolutionV202007 {
    public int maxCoins(int[] nums) {
        // 扩展原数组为 nums2 ，收尾增加值 1，方便计算
        int[] nums2 = new int[nums.length + 2];
        nums2[0] = 1;
        nums2[nums2.length - 1] = 1;
        for (int i = 0; i < nums.length; i++) {
            nums2[i + 1] = nums[i];
        }
        // dp[i][j] 表示开区间 (i,j) 能得到的最大金币数
        // 则 dp[i][j] = max_{i<k<j}{dp[i][k] + dp[k][j] + nums2[i] * nums2[k] * nums2[j]}, 且 dp[0][nums2.length - 1] 就是最终结果
        int[][] dp = new int[nums2.length][nums2.length]; // 默认初始值都是 0

        // 遍历填表，由于 dp[i][j] 依赖于 dp[k][j] 而 k > i，即第 i 行的结果依赖行数大于 i 的结果，所以要 i 要从 nums2.length-1 开始递减遍历
        for (int i = nums2.length - 2; i >= 0; i--) {
            for (int j = 0; j < nums2.length; j++) {
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + nums2[i] * nums2[k] * nums2[j]);
                }
            }
        }
        return dp[0][nums2.length - 1];
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_312_BurstBalloons.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_312_BurstBalloons.java

---