戳气球的最大得分问题（环形数组版本） 题目描述 给定一个长度为n的环形数组nums，每个元素nums[ i]表示气球上的数字。游戏规则：戳破第i个气球可以获得nums[ i-1] * nums[ i] * nums[ i+1]的分数（超出边界的值视为1），然后nums[ i ]被移除。重复这个过程直到所有气球被戳破。求能获得的最大总分数。 解题思路 将环形数组转换为线性数组：复制数组接在原数组末尾，长度变为2n 定义dp[ i][ j ]表示戳破区间(i,j)内所有气球能获得的最大分数（开区间，不含i和j） 状态转移：假设最后戳破的气球是k，则得分 = dp[ i][ k] + dp[ k][ j] + nums[ i] nums[ k] nums[ j ] 最终答案为所有长度为n的区间中的最大值 详细步骤 步骤1：处理环形结构 由于是环形数组，我们在原数组nums首尾各添加一个1（虚拟边界），然后复制一份接在后面： 新数组arr = [ 1] + nums + [ 1] + [ 1] + nums + [ 1 ] 实际计算时只需考虑长度为n+2的窗口在这个扩展数组上滑动 步骤2：定义状态 定义dp[ i][ j ]为戳破区间(i,j)内所有气球能获得的最大分数（开区间） i和j表示边界，不戳破 区间长度至少为2（i和j之间要有气球） 步骤3：状态转移方程 对于区间(i,j)，枚举最后戳破的气球k（i < k < j）： 戳破k时，旁边最近的气球是i和j（因为区间内其他气球已戳破） 得分 = dp[ i][ k] + dp[ k][ j] + arr[ i] arr[ k] arr[ j ] dp[ i][ j ]取所有k中的最大值 步骤4：初始化 区间长度为2时（没有气球可戳）：dp[ i][ i+1 ] = 0 从小区间向大区间递推 步骤5：计算顺序 按区间长度len从2到n+1遍历： 遍历区间起点i从0到2n-len 计算终点j = i+len 遍历k从i+1到j-1更新dp[ i][ j ] 步骤6：寻找最大值 在扩展数组上，最大得分为所有长度为n+2的区间中的最大值： max(dp[ i][ i+n+1 ])，其中i从0到n-1 示例演示 假设nums = [ 3,1,5,8 ]（环形） 扩展后arr = [ 1,3,1,5,8,1,1,3,1,5,8,1 ] 计算dp[ 0][ 5 ]对应原环形数组的最大得分： 最后戳破1：得分 = dp[ 0][ 2] + dp[ 2][ 5] + 1 1 1 最后戳破5：得分 = dp[ 0][ 3] + dp[ 3][ 5] + 1 5 1 最后戳破8：得分 = dp[ 0][ 4] + dp[ 4][ 5] + 1 8 1 取最大值即为环形情况下的解 复杂度分析 时间复杂度：O(n³)（三层循环） 空间复杂度：O(n²)（DP表） 这种解法通过扩展数组巧妙处理了环形结构，保持了区间DP的核心思想。