区间动态规划例题：戳气球问题（环形版本） 题目描述 给定一个环形数组 nums ，表示一排气球，每个气球上标有一个数字。你被要求戳破所有气球。戳破第 i 个气球时，你可以获得 nums[left] * nums[i] * nums[right] 的分数，其中 left 和 right 是当前状态下与 i 相邻的气球。戳破 i 后， left 和 right 会变成相邻。求戳破所有气球能获得的最大分数。 环形处理 ：由于是环形，首尾气球相邻。例如 nums = [3,1,5,8] 在环形中，戳破最后一个气球 8 时，相邻的是 5 和 3 。 解题思路 问题转化 ：将环形数组拆解为线性数组。通过复制数组并拼接（如 nums 变为 [3,1,5,8,3,1,5] ），但更高效的方法是：在原数组首尾各添加一个虚拟气球（值为1），然后任意选择一个位置作为起点，转化为线性问题。 实际技巧：将原数组扩展为 [1] + nums + [1] ，然后在这个长度为 n+2 的线性数组上求解 戳破所有中间气球（保留首尾的1）的最大分数 。 区间动态规划定义 ： 设 dp[i][j] 表示戳破区间 (i, j) 内所有气球（ 不包含端点 i 和 j ）能获得的最大分数。区间端点 i 和 j 保留不戳破。 最终目标是求 dp[0][n+1] ，其中 n 是原数组长度，因为扩展后数组索引为 0 到 n+1 ，两端值为1。 状态转移 ： 对于区间 (i, j) ，假设最后一个被戳破的气球是 k （ i < k < j ）。戳破 k 时，其相邻气球是 i 和 j （因为区间内其他气球已被戳破），因此得分是 nums[i] * nums[k] * nums[j] 。 戳破 k 前，需要先戳破 (i, k) 和 (k, j) 内的气球，这两部分互不影响。因此： dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]) ，其中 k 遍历 i+1 到 j-1 。 计算顺序 ： 区间长度 len 从 2 开始到 n+1 （因为区间至少包含一个气球时 len=3 ，即 i 和 j 之间有一个索引）。 对于每个区间长度，遍历所有起点 i ，计算终点 j = i + len 。 详细步骤 扩展数组为 [1] + nums + [1] ，新长度 n+2 。 初始化 dp 为 (n+2) x (n+2) 的二维数组，初始值为0。 遍历区间长度 len 从 2 到 n+1 ： 对于每个起点 i ，终点 j = i + len （需满足 j ≤ n+1 ）。 遍历 k 从 i+1 到 j-1 ，更新： dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]) 。 返回 dp[0][n+1] 。 示例 （ nums = [3,1,5,8] ） 扩展数组： [1,3,1,5,8,1] ， n=4 。 计算区间： len=2 ：区间如 (0,2) ，只有一个气球 k=1 ，得分= 1*3*1=3 。 逐步合并，最终 dp[0][5] 为最大分数：戳破顺序可选 1,3,5,8 等，最优解为167（具体计算略）。 通过以上步骤，环形问题被转化为线性动态规划，确保无后效性且覆盖所有可能顺序。