戳气球的最大得分问题（环形版本）

题目描述：
给定一个环形数组nums，表示每个气球上的数字。环形数组意味着首尾相连。现在要戳破所有气球，戳破第i个气球可以获得nums[left] * nums[i] * nums[right]的分数，其中left和right是第i个气球相邻的气球。当第i个气球被戳破后，left和right气球变成相邻。求能获得的最大分数。

解题过程：

1. 问题分析
   这是一个环形区间动态规划问题。与线性版本不同，环形数组意味着第一个和最后一个气球相邻，这增加了问题的复杂性。

2. 环形转线性技巧
   我们可以通过复制数组来将环形问题转化为线性问题。具体来说：

• 将原数组复制一份接在后面，形成长度为2n的新数组
• 在这个新数组上，原问题等价于在长度为n的任意连续子数组中求解线性戳气球问题

3. 状态定义
   定义dp[i][j]表示戳破区间(i,j)内所有气球能获得的最大分数，注意这里是开区间，即i和j位置的气球不戳破。

4. 状态转移方程
   对于区间(i,j)，我们考虑最后一个被戳破的气球k（i < k < j）：
   dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])

5. 初始化

• 当区间长度小于等于1时，dp[i][j] = 0（没有气球可戳）
• 对角线初始化为0

6. 遍历顺序
   按区间长度从小到大遍历，确保计算大区间时所需的小区间都已计算完成。

7. 算法步骤

1. 如果数组为空，返回0
2. 创建新数组arr，长度为n+2，首尾为1，中间为原数组
3. 创建dp数组，大小为(n+2)×(n+2)，初始化为0
4. 对于区间长度len从2到n+1：
   对于左端点i从0到n+1-len：
     设置j = i + len
     对于分割点k从i+1到j-1：
       dp[i][j] = max(dp[i][j], 
                     dp[i][k] + dp[k][j] + arr[i]*arr[k]*arr[j])
5. 返回dp[0][n+1]

8. 复杂度分析

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

9. 示例演示
   对于nums = [3,1,5,8]：

• 构造arr = [1,3,1,5,8,1]
• 计算过程按区间长度递增
• 最终结果dp[0][5] = 167

这个解法通过添加边界值1，将环形问题转化为线性问题，是处理环形区间DP的常用技巧。