戳气球的最大得分问题（基础版本） 题目描述： 给定一个长度为n的数组nums，表示一排气球，每个气球上标有一个数字。当你戳破一个气球i时，你可以获得nums[ left] × nums[ i] × nums[ right ]的分数，其中left和right是气球i相邻的左右气球。戳破气球i后，left和right变成相邻。求戳破所有气球能获得的最大分数。 解题过程： 问题分析： 当我们戳破一个气球时，得分取决于该气球和其左右相邻气球的值 戳破气球后，相邻关系会改变，这会影响后续戳破的得分 我们需要找到戳破气球的顺序，使得总得分最大 关键思路转换： 与其考虑"先戳破哪个气球"，不如考虑"最后一个戳破哪个气球" 如果气球k是最后一个被戳破的，那么： 在戳破k之前，区间[ 0, k-1]和[ k+1, n-1 ]的气球已经被戳破 戳破k时，它的左右邻居就是整个区间的边界 动态规划定义： 定义dp[ i][ j ]表示戳破区间(i, j)内所有气球能获得的最大分数 注意：这里区间是开区间(i, j)，不包括i和j位置的气球 我们在原数组两端各添加一个值为1的气球，即新数组为[ 1, nums[ 0], nums[ 1], ..., nums[ n-1], 1 ] 状态转移方程： 对于区间(i, j)，枚举最后一个戳破的气球k（i < k < j） 戳破k时的得分 = nums[ i] × nums[ k] × nums[ j ] 总得分 = 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 ]) 初始化： 当区间长度小于3时（即i+1 ≥ j），区间内没有气球，dp[ i][ j ] = 0 计算顺序： 按区间长度从小到大计算 先计算长度为3的区间，然后长度为4，直到长度为n+2 算法步骤： 创建新数组arr = [ 1] + nums + [ 1 ]，长度为n+2 初始化dp为(n+2)×(n+2)的二维数组，初始值为0 对于区间长度len从3到n+2（因为包含两端的虚拟气球） 对于区间起点i从0到n+2-len 计算区间终点j = i + len - 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²)