戳气球的最大得分问题（状态转移优化版本） 题目描述： 给定n个气球，每个气球上标有一个数字，这些数字存储在数组nums中。现在要求你戳破所有的气球。当你戳破第i个气球时，你可以获得nums[ left] × nums[ i] × nums[ right ]个硬币，其中left和right代表与第i个气球相邻的气球。戳破第i个气球后，left和right气球就变成相邻的气球。求能获得的最大硬币数量。 注意： 你可以假设nums[ -1] = nums[ n ] = 1，但它们不是真实存在的气球，所以不会被戳破 0 ≤ n ≤ 500 0 ≤ nums[ i ] ≤ 100 解题思路： 问题分析 这是一个经典的区间动态规划问题。关键在于当我们戳破一个气球时，左右两个原本不相邻的气球会变成相邻，这打破了子问题之间的独立性。我们需要找到一种方法将问题分解为相互独立的子问题。 关键思路转变 与其考虑"先戳哪个气球"，不如考虑"最后一个戳破的气球是哪个"。当我们确定最后一个戳破的气球k时，问题被自然地分成了两个独立的子问题：戳破k左边所有气球和戳破k右边所有气球。 状态定义 定义dp[ 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时，dp[ i][ j ] = 0（没有气球可戳） 我们添加两个虚拟气球在首尾，值都为1 计算顺序 由于大区间依赖于小区间，我们需要按照区间长度从小到大计算。 解题步骤： 步骤1：预处理数组 在原始数组首尾各添加一个值为1的气球： [ 1] + nums + [ 1 ] 步骤2：初始化DP表 创建一个二维数组dp，大小为(n+2)×(n+2)，初始化为0 步骤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] + nums[ i] × nums[ k] × nums[ j ] 更新dp[ i][ j] = max(dp[ i][ j ], score) 步骤4：返回结果 dp[ 0][ n+1 ]就是最终的最大得分 示例演示： 假设nums = [ 3, 1, 5, 8 ] 预处理后：balloons = [ 1, 3, 1, 5, 8, 1 ] 计算过程： 区间长度2：[ 0,2]、[ 1,3]、[ 2,4]、[ 3,5 ]等 区间长度3：[ 0,3]、[ 1,4]、[ 2,5 ]等 区间长度4：[ 0,4]、[ 1,5 ]等 区间长度5：[ 0,5 ]（最终结果） 对于区间[ 0,5 ]，枚举最后一个戳破的气球： k=1：dp[ 0][ 1] + dp[ 1][ 5 ] + 1×3×1 = 0 + 167 + 3 = 170 k=2：dp[ 0][ 2] + dp[ 2][ 5 ] + 1×1×1 = 3 + 40 + 1 = 44 k=3：dp[ 0][ 3] + dp[ 3][ 5 ] + 1×5×1 = 8 + 40 + 5 = 53 k=4：dp[ 0][ 4] + dp[ 4][ 5 ] + 1×8×1 = 13 + 8 + 8 = 29 最大值为170 最终结果：dp[ 0][ 5 ] = 170 这个优化版本的关键在于通过改变思考角度（最后戳破的气球）和定义开区间，使得子问题相互独立，从而可以用动态规划高效解决。