题目描述

有 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 =  315      +   358      +    138      +   181   = 167

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/burst-balloons
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法1 – dp

我们将气球的长度len作为子问题,先考虑能够从长度较短的气球序列能获得的最大值,那么更长的气球序列可以从较短的气球序列增加气球得到。定义一个二维数组dp[i][j],表示戳破第i个到第j个气球能获得的最大值,j-i+1就是气球序列的长度len。我们再从i到j找一个分割点k,第k个气球保留到最后戳破。那么有:

dp[i][j] = max(dp[i][j], dp[i][k-1] + dp[k+1][j] + nums[k]*nums[i-1]*nums[j+1])
注意:当i-1<0或j+1>=|nums|时取1(虚拟气球),当k-1<0或k+1>=|nums|时dp[i][k-1], dp[k+1][j]取0;
我们将题目说明部分提到的“你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。“称之为分值为1的虚拟气球。
图1 – nums数组

图1绘制了从nums数组计算dp[i][j]的示意图,为了下面描述方便我们将nums长度|nums|记为n。填充dp数组由3重循环实现,第一层循环更新len=1…n;第二层循环更新子序列左边界i=0…n-len, 那么右边界j=i+len-1;第三层循环更分割点k=i…j,我们计算完上面的i, j, k变量就可以填充上面的dp[i][j]了。

在实现中需要注意,计算k-1, k+1, i-1, j+1可能会越界。当访问dp数组越界我们就替换成0(因为当分割点是第一个元素或者最后一个元素,分割点左边的序列或者右边序列不存在),当访问nums数组越界我们就替换成1(虚拟气球)。

该解法的时间复杂度为O(n^3),空间复杂度为O(n^2),全部代码如下:

class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int n = nums.length;
        int[][] dp = new int[n][n];

        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1;
                for (int k = i; k <= j; k++) {
                    int left = k - 1 >= 0 ? dp[i][k - 1] : 0;
                    int right = k + 1 < n && j - 1 >= 0 ? dp[k + 1][j] : 0;
                    int rest = (i - 1 >= 0 ? nums[i - 1] : 1) * (j + 1 < n ? nums[j + 1] : 1) * nums[k];
                    dp[i][j] = Math.max(dp[i][j], left + right + rest);
                }
            }
        }

        return dp[0][n - 1];
    }
}

可以看到,上面的代码对于边界条件有很多判断。为了简化实现,我们可以在nums数组的左右两边各插入一个分值为1的气球,这样我们在访问nums数组的时候就不会越界,省去了很多if…else…。

class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int n = nums.length;
        int[] paddingNums = new int[n + 2];
        int[][] dp = new int[n + 2][n + 2];

        paddingNums[0] = 1;
        paddingNums[paddingNums.length - 1] = 1;
        System.arraycopy(nums, 0, paddingNums, 1, n);

        for (int len = 1; len <= n; len++) {
            for (int i = 1; i <= n + 1 - len; i++) {
                int j = i + len - 1;
                for (int k = i; k <= j; k++) {
                    int v = dp[i][k - 1] + dp[k + 1][j] + paddingNums[i - 1] * paddingNums[j + 1] * paddingNums[k];
                    dp[i][j] = Math.max(dp[i][j], v);
                }
            }
        }

        return dp[1][n];
    }
}
pwrliang Dynamic Programming ,

Leave a Reply

Your email address will not be published. Required fields are marked *