Keshawn_lu's Blog

Leetcode 312. 戳气球

动态规划
字数统计: 683阅读时长: 3 min
2020/07/19 Share

题目简介：

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

现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

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

说明:

  • 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:

1
2
3
4
输入: [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

思路：

动态规划，dp[i][j]代表将开区间(i, j)内的所有气球戳爆后所能获得的最大硬币数量。

为处理边界问题，先将nums的最前面和最后面插入1。

由于是开区间，所以i的取值为0 ~ n - 1(n为没插入1前的数组长度)，第一个气球为nums[0] = 1，最后一个气球为nums[n] = 1，所以若i >= n，则没有气球可以戳了。

j的取值为i + 2 ~ n + 1，若j < i + 2，则开区间里没有气球可以戳了。

所以在(i, j)区间里循环定义k，即k的取值为i + 1 ~ j - 1。

k的左边最大硬币数为dp[i][k]，k的右边最大硬币数为dp[k][j]，将这些气球都戳爆后，最后戳nums[k]这个气球，获得的硬币数为nums[i] * nums[k] * nums[j]。(因为一定有一个是最后被戳爆的气球，所以循环遍历，找出硬币数最大值时的那个k即可)。

所以dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])。

最后返回dp[0][n + 1]，即不要最开始和最后面我们插入的那两个气球，只要中间的1,2, ..., n个气球。

tip:

  • i, j, k的边界值比较重要，需要理解清楚。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int maxCoins(vector<int>& nums) {

        int n = nums.size();

        nums.push_back(1);
        nums.insert(nums.begin(), 1);

        //(i, j)区间内，戳破所有气球所能获得的最大硬币数
        vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));

        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 coins = nums[i] * nums[k] * nums[j];
                    //(i, k) + k + (k, j)
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + coins);
                }
            }
        }

        return dp[0][n + 1];
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网