戳气球问题（基础版本）

题目描述：
给定一个长度为n的数组nums，表示n个气球，每个气球上标有一个数字。你的目标是戳破所有气球。当你戳破第i个气球时，你可以获得nums[i-1] * nums[i] * nums[i+1]枚硬币（假设nums[-1] = nums[n] = 1）。戳破所有气球后，求能获得的最大硬币数量。

解题过程：

1. 问题分析：

• 戳破气球的顺序会影响最终获得的硬币总数
• 当戳破一个气球时，获得的硬币与相邻气球的值相关
• 需要找到最优的戳破顺序来最大化总硬币数

2. 关键思路：

• 考虑逆向思维：不是先戳哪个气球，而是最后戳哪个气球
• 当确定最后戳破的气球时，它左右两边的区间是相互独立的
• 使用dp[i][j]表示戳破区间(i,j)内所有气球能获得的最大硬币数

3. 状态定义：

• 在数组首尾添加值为1的虚拟气球，新数组为vals，长度为n+2
• dp[i][j]：戳破区间(i,j)内所有气球（不包括i和j位置）能获得的最大硬币数
• 最终目标是求dp[0][n+1]

4. 状态转移方程：

• 对于区间(i,j)，枚举最后戳破的气球k（i < k < j）
• 当最后戳破气球k时，获得的硬币为vals[i] * vals[k] * vals[j]
• 同时加上左右两个区间的最大值：dp[i][k] + dp[k][j]
• 状态转移方程：dp[i][j] = max(dp[i][j], vals[i] * vals[k] * vals[j] + dp[i][k] + dp[k][j])

5. 初始化：

• 当区间长度小于3时（即i+1 ≥ j），dp[i][j] = 0
• 因为区间内没有气球可戳破

6. 计算顺序：

• 按区间长度从小到大计算
• 先计算长度为3的区间，然后是4，5，...，直到n+2

7. 算法步骤：

1. 创建新数组vals = [1] + nums + [1]，长度为n+2
2. 初始化dp数组，大小为(n+2)×(n+2)，初始值为0
3. 对于区间长度len从3到n+2：
   对于左端点i从0到n+2-len：
      令j = i + len - 1
      对于k从i+1到j-1：
          dp[i][j] = max(dp[i][j], vals[i]*vals[k]*vals[j] + dp[i][k] + dp[k][j])
4. 返回dp[0][n+1]

8. 示例验证：
   假设nums = [3,1,5,8]
   vals = [1,3,1,5,8,1]
   计算过程：

• 区间(0,2)：最后戳破气球1，得1×3×1 + 0 + 0 = 3
• 区间(1,3)：最后戳破气球2，得3×1×5 + 0 + 0 = 15
• 区间(2,4)：最后戳破气球3，得1×5×8 + 0 + 0 = 40
• 区间(0,3)：枚举k=1和k=2，取最大值
• 依此类推，最终得到最大硬币数

时间复杂度：O(n³)，空间复杂度：O(n²)