当前为游客只读模式。登录后可提交代码判题并保存草稿与进度。
戳气球
困难maxCoins()时间限制 2000 ms内存限制 128 MB复杂度要求 时间 O(n^3)，空间 O(n^2)
戳气球
有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。当你戳破气球 i 时，你可以获得 nums[left] nums[i] nums[right] 个硬币。这里的 left 和 right 代表和 i 相邻的没有被戳破的两个气球。戳破后，left 和 right 就变成了相邻的。
求你能获得的最大硬币数。
你可以假设 nums[-1] = nums[n] = 1（边界处相当于虚拟气球，不实际戳破）。
约定
1 <= nums.length <= 3000 <= nums[i] <= 100
输入
nums：每个气球上的数字
输出
能获得的最大硬币数。
示例一
输入：
nums = [3, 1, 5, 8]输出：
167解释：nums = [3,1,5,8] → 戳 1 得 315=15 → [3,5,8] → 戳 5 得 358=120 → [3,8] → 戳 3 得 138=24 → [8] → 戳 8 得 181=8。总计 167。
示例二
输入：
nums = [1, 5]输出：
10复杂度要求
- 时间复杂度：
O(n^3) - 空间复杂度：
O(n^2)
Loading...
输入
[[3,1,5,8]]
预期输出
167