LeetCode312.戳气球【动态规划】【Java】【困难】

目录

英文描述

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

中文描述

有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1 或 i + 1 超出了数组的边界，则当它是一个数字为 1 的气球。

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

示例与说明

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

参考 @狗大王【[这个菜谱, 自己在家也能做] 关键思路解释】

本题的核心思想是动态规划。具体步骤如下：

1. 对于区间 (i, j) 内的每一个气球 k，假设 k 是最后一个被戳破的气球。用 dp[i][j] 记录区间 (i, j) 内的最大得分。
2. 这样 dp[i][j] = dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]。
3. 其中 dp[i][k] 和 dp[k][j] 可以通过递归求解。

Java

class Solution {
    public int maxCoins(int[] nums) {
        int newLen = nums.length + 2;
        int[] newNums = new int[newLen];
        // 创建新数组，左右两边添加1，便于处理边界情况
        newNums[0] = 1;
        newNums[newLen - 1] = 1;
        for (int i = 0; i