1.题目基本信息

1.1.题目描述

有 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.2.题目地址

https://leetcode.cn/problems/burst-balloons/description

2.解题方法

2.1.解题思路

动态规划+逆向转拿出气球为填入气球

2.2.解题步骤

第一步，状态定义;逆着放置,往i气球和j气球之间塞满气球,能得到的最大金币数,其中i

第二步，状态转移;dp[i][j]=max(nums2[i]*nums2[j]*nums2[mid]+dp[i][mid]+dp[mid][j]),这里的i0；j>i+1，j从i+2->length+1；k从i+1->j-1；上面的都是闭区间

第三步，返回结果

3.解题代码

Python代码

class Solution:
    # 思路：动态规划+逆向转拿出气球为填入气球
    def maxCoins(self, nums: List[int]) -> int:
        length=len(nums)
        nums2=[1]+nums+[1]
        # 第一步，状态定义;逆着放置,往i气球和j气球之间塞满气球,能得到的最大金币数,其中i<j-1,是开区间
        dp=[[0]*(length+2) for i in range(length+2)]
        # 第二步，状态转移;dp[i][j]=max(nums2[i]*nums2[j]*nums2[mid]+dp[i][mid]+dp[mid][j]),这里的i<j-1，其余的条件下dp[i][j]=0。其中因为i<j-1，j最大为length+1，所以i从length-1->0；j>i+1，j从i+2->length+1；k从i+1->j-1；上面的都是闭区间
        for i in range(length-1,-1,-1):
            for j in range(i+2,length+2):
                for mid in range(i+1,j):
                    dp[i][j]=max(dp[i][j],nums2[i]*nums2[j]*nums2[mid]+dp[i][mid]+dp[mid][j])
        # print(dp)
        # 第三步，返回结果
        return dp[0][length+1]

C++代码

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int length=nums.size();
        vector<int> nums2(length+2,1);
        for(int i=0;i<length;++i){
            nums2[i+1]=nums[i];
        }
        vector<vector<int>> dp(length+2,vector<int>(length+2,0));
        for(int i=length-1;i>-1;--i){
            for(int j=i+2;j<length+2;++j){
                for(int mid=i+1;mid<j;++mid){
                    dp[i][j]=max(dp[i][j],nums2[i]*nums2[j]*nums2[mid]+dp[i][mid]+dp[mid][j]);
                }
            }
        }
        return dp[0][length+1];
    }
};

4.执行结果