博客

题目描述

有 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

思路

动态规划 （区间DP）O（n^3）


状态数量n平方，转移时间复杂度O(n)，总共是三次方

1. f[i, j]
   
   表示将区间[i + 1, j – 1]气球打完的所有方案的最大值
   
   ，（注：不表示[i, j]气球的原因是，算左边边界倒数第二个气球时要用到两个边界的值，所以需要保证左右两个边界不被打掉）。
   
   
2. 状态转化计算，根据最后一次打气球的位置来划分集合（可能从i + 1到j – 1，用一个变量k来枚举位置）。 这样的情况下：理解为先把[i, k]打完，然后再把[k,j]打完，最后打第k个位置。
   
   
3. 为了方便在左右两个边界补上1，且保证两个边界1不会被打掉。
4. 区间dp套路：先枚举长度，再枚举起点，因为两个边界要固定。

代码

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        //便于计算，插入左右两个边界1
        int a[] = new int[n + 2];
        Arrays.fill(a, 1);
        for (int i = 1; i <= n; i ++ ) {
            a[i] = nums[i - 1];
        }
        //状态数组
        int dp[][] = new int[n + 2][n + 2];
        //区间dp先枚举区间长度，最小为3，因为左右1边界不能打掉，如果为2的话相等于没有气球
        //再枚举左端点，同时固定右端点，随后在中间枚举k 最后一次打掉的可能位置
        for (int len = 2; len <= n + 2; len ++ ) {
            for (int i = 0; i + len - 1 <= n + 1; i ++ ) {
                int j = i + len - 1;
                //状态计算，枚举最后一次打的可能位置
                for (int k = i + 1; k < j; k ++ ) {
                    //两边打完,这里不用写[i,k - 1]因为状态表示里面本身没有算两个端点
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[j] * a[k]);
                }
            }
        }
    return dp[0][n + 1];
    }
}