戳气球问题（环形版本） 题目描述： 有 n 个气球，编号为 0 到 n-1，每个气球上标有一个数字，这些数字存储在数组 nums 中。现在要求戳破所有的气球。如果戳破气球 i，可以获得 nums[ left] × nums[ i] × nums[ right ] 的分数，其中 left 和 right 是气球 i 的相邻气球。（当气球 i 被戳破后，left 和 right 会变成相邻气球。）目标是获得的最大分数。 注意：这里的 nums 数组表示一个环形，即 nums[ -1] 是 nums[ n-1] 的下一个，nums[ n] 是 nums[ 0 ] 的前一个。你需要处理环形结构。 解题过程： 问题分析： 在环形版本中，气球排列成一个圈，首尾相连。 戳破一个气球后，相邻关系会动态改变，这增加了问题的复杂性。 关键思路：将环形问题转化为线性问题。可以通过复制数组并考虑所有可能的起点来模拟环形结构。 状态定义： 定义 dp[ i][ j ] 表示戳破区间 (i, j) 内所有气球（不包括 i 和 j 本身）所能获得的最大分数。 注意：在区间 (i, j) 中，i 和 j 是边界气球，不被戳破，用于计算分数。 状态转移方程： 假设在区间 (i, j) 中，最后一个被戳破的气球是 k（i < k < j）。 戳破 k 时，其相邻气球是 i 和 j（因为区间内其他气球已被戳破）。 因此，戳破 k 的分数是 nums[ i] × nums[ k] × nums[ j ]。 总分数为：dp[ i][ k]（戳破 i 到 k 之间的气球） + dp[ k][ j]（戳破 k 到 j 之间的气球） + nums[ i] × nums[ k] × nums[ j ]。 状态转移方程：dp[ i][ j] = max(dp[ i][ j], dp[ i][ k] + dp[ k][ j] + nums[ i] × nums[ k] × nums[ j ])，其中 k 遍历 (i, j) 中的所有可能位置。 初始化： 当区间长度小于 2 时（即 j - i <= 1），区间内没有气球可戳破，dp[ i][ j ] = 0。 环形处理： 将原数组 nums 复制一份，形成新数组 arr，长度为 2n。 在新数组上，对于每个长度为 n 的区间（即环形中的连续 n 个气球），计算 dp[ i][ i+n ] 的最大值。 最终答案是所有可能起点的 dp[ i][ i+n ] 中的最大值。 计算顺序： 按区间长度从小到大计算 dp 值。 外层循环遍历区间长度 len，从 2 开始到 n（因为 j - i >= 2 时区间内才有气球）。 内层循环遍历区间起点 i，计算终点 j = i + len。 对于每个区间 (i, j)，遍历所有可能的 k（i < k < j），更新 dp[ i][ j ]。 示例： 假设 nums = [ 3, 1, 5, 8 ]。 复制后 arr = [ 3, 1, 5, 8, 3, 1, 5, 8 ]。 计算所有长度为 4 的区间（如 [ 3,1,5,8]、[ 1,5,8,3] 等）的 dp[ i][ i+4 ] 最大值。 复杂度分析： 时间复杂度：O(n³)，因为有三层循环（区间长度、起点、分割点）。 空间复杂度：O(n²)，用于存储 dp 表。 通过以上步骤，可以解决环形戳气球问题，确保你理解了状态定义和环形转线性的技巧。