戳气球的最大得分问题（状态转移优化版本） 题目描述： 给定一个整数数组 nums，表示一排气球上的数字。当你戳破一个气球 i 时，你可以获得 nums[ left] × nums[ i] × nums[ right ] 的分数，其中 left 和 right 是气球 i 的相邻气球。戳破气球 i 后，left 和 right 会变成相邻气球。求戳破所有气球能获得的最大总分数。 解题过程： 问题分析： 戳破气球的过程会改变气球之间的相邻关系 如果从中间开始戳破，分数计算会依赖于后续状态 我们需要找到最优的戳破顺序来最大化总得分 关键思路： 在原始数组首尾添加值为1的虚拟气球，简化边界处理 定义 dp[ i][ j ] 表示戳破区间 (i, j) 内所有气球能获得的最大分数 注意：区间是开区间 (i, j)，即 i 和 j 不被戳破，作为边界 状态转移方程： 对于区间 (i, j)，考虑最后一个被戳破的气球 k (i < k < j)： dp[ i][ j] = max(dp[ i][ j], dp[ i][ k] + dp[ k][ j] + nums[ i] × nums[ k] × nums[ j ]) 优化实现： 按区间长度从小到大进行动态规划 确保计算大区间时，所有小区间都已计算完成 详细步骤： 步骤1：预处理数组 在原始数组首尾各添加一个值为1的气球： 新数组 = [ 1] + nums + [ 1 ] 步骤2：初始化DP表 创建二维数组 dp，大小为 (n+2) × (n+2)，初始化为0 其中 n 是原始数组长度 步骤3：按区间长度递推 对于区间长度 len 从 2 到 n+1： 对于左端点 i 从 0 到 n+1-len： 计算右端点 j = i + len 对于分割点 k 从 i+1 到 j-1： score = dp[ i][ k] + dp[ k][ j] + new_ nums[ i] × new_ nums[ k] × new_ nums[ j ] dp[ i][ j] = max(dp[ i][ j ], score) 步骤4：返回结果 最终结果存储在 dp[ 0][ n+1 ] 中 时间复杂度分析： 三重循环：O(n³) 空间复杂度：O(n²) 示例验证： 输入：nums = [ 3,1,5,8 ] 处理后的数组：[ 1,3,1,5,8,1 ] 计算过程： 先计算长度为2的区间 再计算长度为3的区间 依此类推，直到计算整个区间 最终得到最大分数为167，戳破顺序为：1→5→3→8 这种方法的优势在于将问题转化为区间DP，通过添加边界气球简化计算，确保每个子问题都能正确求解。