戳气球问题（环形版本） 题目描述 有一个由 n 个气球组成的环形数组，每个气球上标有一个数字。你需要戳破所有气球，但戳破第 i 个气球时，会获得 nums[i-1] * nums[i] * nums[i+1] 的得分（若索引越界，则视为乘以 1）。求能获得的最大总得分。 解题思路 环形转线性 ：将原数组复制一份接在末尾，形成长度为 2n 的数组，但只需考虑长度为 n+1 的区间即可覆盖所有环形情况。 定义状态 ：设 dp[l][r] 表示戳破区间 (l, r) 内所有气球（不包含边界 l 和 r ）能获得的最大得分。 状态转移 ：在区间 (l, r) 内，假设最后一个戳破的气球是 k （ l < k < r ），则得分由三部分组成： 左区间 (l, k) 的得分： dp[l][k] 右区间 (k, r) 的得分： dp[k][r] 戳破 k 的得分： nums[l] * nums[k] * nums[r] （因为 k 是区间内最后一个气球，此时左右相邻的是边界气球 l 和 r ） 转移方程： dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + nums[l]*nums[k]*nums[r]) 初始化与计算顺序 ：区间长度从 2 开始（至少包含一个气球），逐步扩大到 n+1 。 结果提取 ：环形数组的最大得分为所有长度为 n+1 的区间中 dp[i][i+n] 的最大值。 示例与验证 以 nums = [3,1,5,8] 为例： 扩展数组为 [3,1,5,8,3,1,5,8] ，但只需计算区间长度 5（即 n+1=5 ）。 通过递推得到 dp[0][4] 、 dp[1][5] 等值，取最大值即为答案 167。 此方法通过破环成链和区间DP，高效解决了环形戳气球问题。