戳气球的最大得分问题（基础版本） 题目描述： 给定一个长度为n的数组nums，代表n个气球，每个气球上标有一个数字。现在你需要戳破所有的气球。当你戳破第i个气球时，你可以获得nums[ left] × nums[ i] × nums[ right ]的分数，其中left和right代表与第i个气球相邻的气球。戳破气球i后，气球left和气球right会变成相邻的气球。 求戳破所有气球能获得的最大分数。 解题过程： 问题分析： 当我们戳破一个气球时，得分取决于该气球和其左右相邻气球的数值 戳破气球后，相邻关系会发生变化，这会影响后续戳气球的得分 我们需要找到一个戳气球的顺序，使得总得分最大化 关键思路： 考虑逆向思维：不是考虑"先戳哪个气球"，而是考虑"最后戳哪个气球" 当我们确定最后一个戳破的气球时，它左右两边的气球是相互独立的子问题 在最后一个气球被戳破时，它的左边和右边边界是确定的 状态定义： 定义dp[ i][ j ]表示戳破区间(i, j)内所有气球能获得的最大分数 注意：这里i和j是开区间边界，不包含在戳破范围内 我们在原数组首尾各添加一个值为1的虚拟气球，表示边界 状态转移方程： 对于区间(i, j)，我们枚举最后一个被戳破的气球k，其中i < k < j 当k是最后一个被戳破的气球时，得分为： dp[ i][ k] + dp[ k][ j] + nums[ i] × nums[ k] × nums[ j ] 状态转移方程： dp[ i][ j] = max(dp[ i][ j], dp[ i][ k] + dp[ k][ j] + nums[ i] × nums[ k] × nums[ j ]) 其中k的取值范围是i+1到j-1 初始化： 当区间长度小于等于1时，dp[ i][ j ] = 0（没有气球可戳） 其他情况初始化为0 计算顺序： 按区间长度从小到大计算 先计算长度小的区间，再计算长度大的区间 算法步骤： 在nums首尾各添加一个1，得到新数组arr 初始化dp数组，大小为(n+2)×(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] + arr[ i] × arr[ k] × arr[ j ]) 最终结果存储在dp[ 0][ n+1 ]中 时间复杂度：O(n³)，空间复杂度：O(n²) 这个解法通过逆向思考和区间DP的思想，将复杂的气球戳破顺序问题转化为相对简单的子问题组合，从而高效地求解最大得分。