leetcode: 312. 戳气球

312. 戳气球

来源：力扣（LeetCode）

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

有 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

示例 2：

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

提示：

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

解法

• 动态规划：前后气球戳破有关联，可以使用暴力搜索或者动态规划，由于暴力搜索复杂度太高，这里只考虑动态规划
  动态规划：四个步骤：
  • 问题定义
  • 状态转移方程
  • 初始条件和边界情况
  • 确定计算顺序（自顶向下，还是自下向上）

问题定义：
找区间范围内的最值问题，可以定义dp[i][j]表示气球区间i到j之间的值，不包含边界。

状态转移方程：

假设最后一次戳k位置，那最后一次的收益就是$dp[i][k]+dp[k][j]+nums[i]\ast nums[j]\ast nums[k]$ （把i～k之间的球按某种最优方式戳完，再把k～j之间的球戳完，最后戳k），那只要循环k保存最大值就可以找到全局最大值

初始化条件和边界条件

• i <= j
• nums = [1] + nums + [1] , 这是由于题目中如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球
• dp = [[0] * len(nums) for _ in range(len(nums))

确定计算顺序:
这个是从上向下的方向计算即可，省略掉很多不必要的计算

代码实现

动态规划

python实现

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        n = len(nums)
        if n == 3:
            return nums[1]
        
        dp = [[0] * n for _ in range(n)]
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                for k in range(i+1, j):
                    dp[i][j] = max(dp[i][j], dp[i][k]+nums[i]*nums[k]*nums[j]+dp[k][j])
        return dp[0][-1]

c++实现

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(), 1);
        nums.insert(nums.end(), 1);
        int n = nums.size();
        vector<vector<int>> dp (n, vector<int>(n, 0));
        for(int i=n-1; i>=0; i--) {
            for(int j=i+1; j<n; j++) {
                for (int k=i+1; k<j; k++) {
                    dp[i][j] = max(dp[i][j], dp[i][k]+nums[i]*nums[k]*nums[j]+dp[k][j]);
                }
            }
        }
        return dp[0][n-1];
    }
};

复杂度分析

• 时间复杂度： $O(n^3)$
• 空间复杂度： $O(n^2)$

参考

• https://leetcode.cn/problems/burst-balloons/solution/lai-zi-bei-da-suan-fa-ke-de-leetcodeti-j-r03x/
• https://leetcode.cn/problems/burst-balloons/solution/chuo-qi-qiu-by-leetcode-solution/