戳气球的最大得分问题（环形数组版本）
题目描述：
给定一个环形数组nums，表示每个气球上的数字。现在你需要戳破所有气球，获得最大得分。戳破第i个气球的得分规则是：nums[left] * nums[i] * nums[right]，其中left和right是当前气球i相邻的气球。戳破气球i后，left和right气球变成相邻。如果是环形数组的首尾相连，求能获得的最大得分。
解题过程：
- 问题分析：
- 这是一个环形区间动态规划问题
- 戳破气球的过程会改变气球之间的相邻关系
- 环形结构可以通过复制数组来处理
- 关键思路：
- 将环形数组转换为线性数组：nums → nums + nums
- 定义dp[i][j]表示戳破区间(i,j)内所有气球能获得的最大得分
- 注意：这里区间是开区间(i,j)，不包括i和j位置的气球
-
状态转移方程：
对于区间(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]) -
详细步骤：
步骤1：处理环形数组
将长度为n的环形数组复制一份，得到长度为2n的线性数组
这样环形问题就转化为了在2n数组上求n长度区间的问题
步骤2：初始化DP表
dp[i][j] = 0，当j - i <= 1时（区间内没有气球可戳）
步骤3：按区间长度遍历
for len in range(2, n+1): # 区间长度从2到n
for i in range(0, 2n - len): # 区间起点
j = i + len # 区间终点
for k in range(i+1, j): # 枚举最后一个戳破的气球
dp[i][j] = max(dp[i][j],
dp[i][k] + dp[k][j] + nums[i] nums[k] * nums[j])
步骤4：计算最终结果
由于是环形，我们需要考虑所有可能的起点：
result = max(dp[i][i+n] for i in range(n))
- 示例说明：
假设nums = [3,1,5,8]
复制后：nums = [3,1,5,8,3,1,5,8]
计算dp[0][4]：
- 考虑k=1：dp[0][1]+dp[1][4]+3×1×8 = 0+?+24
- 考虑k=2：dp[0][2]+dp[2][4]+3×5×8 = ?+?+120
- 考虑k=3：dp[0][3]+dp[3][4]+3×8×8 = ?+0+192
最终在所有起点中取最大值得到环形数组的最大得分。
- 时间复杂度：O(n³)
空间复杂度：O(n²)
这个解法通过将环形问题转化为线性问题，巧妙地解决了环形结构的边界条件问题。