↓Skip to main content

【LeetCode 312】戳气球

·360 words·2 mins
WFUing
Author
WFUing
A graduate who loves coding.
Table of Contents

  • 链接：https://leetcode.cn/problems/burst-balloons/description/

难点
#

本题的难点在于如何控制气球的相邻信息，每一次戳气球都会产生新的相邻的气球，但是很容易有一种做题的直觉，

  • 先判断一个气球，
  • 然后继续判断其左边和右边。

怎么判断呢？可以倒过来看这些操作，将全过程看作是每次添加一个气球。我们定义方法 solve ，令 solve(i, j) 表示将开区间 (i, j) 内的位置全部填满气球能够得到的最多硬币数。由于是开区间，因此区间两端的气球的编号就是 i 和 j，对应着 val[i] 和 val[j]。

val 为加上两端两个1的 nums。

代码
#

很容易得到版本一的代码。

class Solution {
    int[] val = new int[302];

    public int maxCoins(int[] nums) {
        int n = nums.length;
        val[0] = 1;
        val[n+1] = 1;
        for(int i = 1; i <= n; i++) {
            val[i] = nums[i-1];
        }
        return solve(0, n+1);
    }

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

但是报错，TLE。于是加上记忆化搜索。

class Solution {
    public int[][] rec;
    public 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 + 1; 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];
    }
}

按照方法一的思路，我们发现我们可以通过变换计算顺序，从「自顶向下」的记忆化搜索变为「自底向上」的动态规划。

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++) {
                    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];
    }
}