戳气球

有 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 <= 300
• 0 <= 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)