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<j-1,是开区间< p="" style="box-sizing: border-box; outline: 0px !important;">

第二步，状态转移;dp[i][j]=max(nums2[i]*nums2[j]*nums2[mid]+dp[i][mid]+dp[mid][j]),这里的i<j-1，其余的条件下dp[i][j]=0。其中因为i0；j>i+1，j从i+2->length+1；k从i+1->j-1；上面的都是闭区间

第三步，返回结果

3.解题代码

Python代码

C++代码

4.执行结果