戳气球问题（基础版本） 题目描述 给定一个长度为 n 的整数数组 nums，表示一排气球，每个气球上的数字。当你戳破一个气球 i 时，你可以获得 nums[ i-1] * nums[ i] * nums[ i+1 ] 枚硬币（假设超出边界的数字为 1）。戳破后，气球 i 消失，左右气球相邻。求戳破所有气球能获得的最大硬币数。 解题思路 问题分析 ：若按顺序戳气球，每一步的得分依赖当前剩余气球的相邻关系，决策顺序会影响后续得分。直接枚举戳气球的顺序（n ! 种可能）不可行。 关键转化 ：将“戳气球”改为“加气球”。定义开区间 (i, j)，表示仅处理区间内未戳的气球，且区间两端的气球 i 和 j 始终存在（不戳破）。问题转化为在 (i, j) 内选择第一个加入的气球，使其得分由左右边界的现有气球决定。 状态定义 ：设 dp[ i][ j] 表示开区间 (i, j) 内能获得的最大硬币数（i 和 j 不戳破，i+1 到 j-1 为可操作气球）。答案为 dp[ 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]) 计算顺序 ：区间长度 len 从 2 到 n+1（开区间至少包含 1 个气球），枚举左端点 i，计算右端点 j = i + len，再枚举 k。 详细步骤 扩展数组为 [ 1] + nums + [ 1 ]，长度 n+2。 初始化 dp 为 (n+2) x (n+2) 的零矩阵。 按区间长度循环： for len in range(2, n+2): for i in range(0, n+2 - len): j = i + len for k in range(i+1, j): dp[ i][ j] = max(dp[ i][ j], dp[ i][ k] + dp[ k][ j] + arr[ i] * arr[ k] * arr[ j ]) 返回 dp[ 0][ n+1 ]。 举例说明 nums = [ 3, 1, 5 ] 扩展后 arr = [ 1, 3, 1, 5, 1 ] 区间 (0, 4)：枚举 k=1,2,3 k=1：得分 = 1 3 1 + dp[ 0][ 1] + dp[ 1][ 4 ] = 3 + 0 + 0 = 3 k=2：得分 = 1 1 5 + dp[ 0][ 2] + dp[ 2][ 4] = 5 + (k=1 时区间(0,2)得分 1 3 1=3) + 0 = 5+3=8 k=3：得分 = 1 5 1 + dp[ 0][ 3] + dp[ 3][ 4] = 5 + (区间(0,3)最大得分：先戳 k=2 得 1 1 1=1，再戳 k=1 得 1 3 1=3，共 4) + 0 = 5+4=9 最大值 = max(3, 8, 9) = 9（顺序：先戳 1，再戳 5，最后戳 3）。