LeetCode 312.戳气球

2023 年 01 月 28 日

515 次浏览

1301字数

# LeetCode 312.戳气球

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

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

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

> 编者注：请务必理解题意，题目的要求是返回 所有可能 中的 最大值，气球被戳爆后，在下一状态是不存在的，[2 3 1 4] -> [2 3 4]

## 动态规划 (容易理解)

推荐配合 [郭郭老师](https://leetcode.cn/u/venturekwok/) 的 [视频](https://www.bilibili.com/video/av631528583) 理解动归的思路

```java
public int maxCoins(int[] nums) {
        int len = nums.length;
        int[] arr = new int[len + 2];
        int[][] dp = new int[len + 2][len + 2];
        System.arraycopy(nums, 0, arr, 1, len);
        arr[0] = arr[len + 1] = 1;

//        枚举右指针，从下往上填表
        for (int left = len - 1; left >= 0; left--) {
            for (int right = left + 2; right <= len + 1; right++) {
//                枚举 (left, right) 间的每个位置，作为最后戳爆的气球
//                1 3 1 5 8 1
//                若 5 为最后一个 则结果为 1*5*1 + (1 3 1 5) 和 (5 8 1) 两个情况的结果
//                因此状态转移方程为
//                dp[left][right] = dp[left][mid] + dp[mid][right] + currRs
//                因为 mid ∈ (left, right), 因此每次结果会不同，维护最大值
                for (int mid = left + 1; mid < right; mid++) {
                    int sum = arr[left] * arr[mid] * arr[right];
                    sum += dp[left][mid] + dp[mid][right];
                    dp[left][right] = Math.max(dp[left][right], sum);
                }
            }
        }
        return dp[0][len + 1];
    }
```

## 记忆化搜索

```java
public int maxCoins(int[] nums) {
        int len = nums.length;
//        设置哨兵
        int[] arr = new int[len + 2];
        System.arraycopy(nums, 0, arr, 1, len);
        arr[0] = 1;
        arr[len + 1] = 1;
        int[][] memo = new int[len + 2][len + 2];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return solve(arr, memo, 0, len + 1);
    }

private int solve(int[] arr, int[][] memo, int left, int right) {
//        确保至少有三个，即中间至少有一个元素
        if (left + 1 >= right) {
            return 0;
        }
//        记忆化搜索
        if (memo[left][right] != -1) {
            return memo[left][right];
        }
        for (int i = left + 1; i < right; i++) {
            int sum = arr[left] * arr[i] * arr[right];
            sum += solve(arr, memo, left, i) + solve(arr, memo, i, right);
            memo[left][right] = Math.max(memo[left][right], sum);
        }
        return memo[left][right];
    }
```

最后修改：2023 年 01 月 28 日