戳气球问题（环形版本） 题目描述： 有n个气球，排成一个环形，每个气球上标有一个数字。这些数字用一个长度为n的数组nums表示。现在要求你戳破所有的气球。当你戳破第i个气球时，你可以获得nums[ left] * nums[ i] * nums[ right ]个硬币，其中left和right是第i个气球相邻的气球。戳破第i个气球后，left和right气球变成相邻。求能获得的最大硬币数量。 解题过程： 问题分析： 这是一个环形区间动态规划问题 戳破气球的操作会改变气球之间的相邻关系 我们需要找到戳破气球的顺序，使得总硬币数最大 环形处理技巧： 将环形数组复制一份接在末尾，变成长度为2n的线性数组 这样环形问题就转化为了在长度为2n的数组上的区间DP问题 最终答案在区间长度为n的所有区间中取最大值 动态规划定义： 定义dp[ i][ j ]表示戳破区间(i,j)内所有气球能获得的最大硬币数 注意：区间是开区间(i,j)，不包括i和j位置的气球 这样定义可以简化边界处理 状态转移方程： 对于区间(i,j)，假设最后一个戳破的气球是k（i < k < j） 戳破气球k时，获得的硬币为：nums[ i] * nums[ k] * nums[ j ] 总收益为：dp[ i][ k] + nums[ i] * nums[ k] * nums[ j] + dp[ k][ j ] 状态转移方程：dp[ i][ j] = max(dp[ i][ j], dp[ i][ k] + nums[ i] * nums[ k] * nums[ j] + dp[ k][ j ]) 算法步骤： 将原数组复制一份：newNums = nums + nums 初始化dp数组为0 按区间长度len从2开始遍历（至少需要3个气球） 对于每个区间起点i，计算终点j = i + len 如果j超过2n，则跳过 遍历区间内所有可能的k（i < k < j） 计算并更新dp[ i][ j ] 代码实现要点： 区间长度从2开始，因为至少需要3个点(i,k,j) 最终答案是所有长度为n的区间中的最大值 时间复杂度：O(n³)，空间复杂度：O(n²) 这个解法通过环形转线性的技巧，将问题转化为标准的区间DP问题，通过枚举最后一个戳破的气球来分解子问题。