LeetCode刷题-312. 戳气球_戳气球力扣

力扣刷题笔记（六）

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 的气球。

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

示例 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
1
2
3
4
5

示例 2：

输入：nums = [1,5]
输出：10
1
2

提示：

• n == nums.length
• 1 <= n <= 300
• 0 <= nums[i] <= 100

代码

• 动态规划

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        // 两侧添加虚拟气球，避免状态转移时判断边界（避免越界）
        int[] balloons = new int[n + 2];
        balloons[0] = balloons[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            balloons[i] = nums[i-1];
        }

        int[][] dp = new int[n + 2][n + 2];
        // i从下往上
        for (int i = n; i >= 0; i--) {
            // j从左往右
            for (int j = i + 1; j <= n + 1; j++) {
                // 遍历最后戳破的气球k
                for (int k = i + 1; k <= j - 1; k++) {
                    dp[i][j] = Math.max(dp[i][j], balloons[k] * balloons[i] * balloons[j] + dp[i][k] + dp[k][j]);
                }
            }
        }
        return dp[0][n + 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

笔记

• 动态规划：状态转移方程理解：https://leetcode.cn/problems/burst-balloons/solution/zhe-ge-cai-pu-zi-ji-zai-jia-ye-neng-zuo-guan-jian-/

  dp[i][j] = x 表示，戳破气球 i 和气球 j 之间（开区间，不包括 i 和 j）的所有气球，可以获得的最高分数为 x。
  dp[i][j] = Math.max(balloons[k] * balloons[i] * balloons[j] + dp[i][k] + dp[k][j]);其中，dp[i][j]是k遍历闭区间[i+1, j-1]得到的结果取最大值。

• 关键点：这个问题中我们每戳破一个气球 nums[i]，得到的分数和该气球相邻的气球 nums[i-1] 和 nums[i+1] 是有相关性的。运用动态规划算法的一个重要条件：子问题必须独立。所以对于这个戳气球问题，如果想用动态规划，必须巧妙地定义 dp 数组的含义，避免子问题产生相关性，才能推出合理的状态转移方程。

我开源了一份武林秘籍，欢迎⭐️star：

• https://gitee.com/lexiaoyuan/the-priceless-treasure-of-wulin
• https://github.com/lexiaoyuan/The-Priceless-Treasure-of-Wulin

创作不易，喜欢的话加个关注点个赞，❤谢谢谢谢❤