[特殊字符] 第85课:戳气球

想系统提升编程能力、查看更完整的学习路线欢迎访问 AI Compasshttps://github.com/tingaicompass/AI-Compass仓库持续更新刷题题解、Python 基础和 AI 实战内容适合想高效进阶的你。 第85课:戳气球模块:动态规划 |难度:Hard ⭐LeetCode 链接:https://leetcode.cn/problems/burst-balloons/前置知识:第71-84课(动态规划基础)预计学习时间:40分钟 题目描述给你一个数组nums,代表一排气球,每个气球上有一个数字。你可以戳破气球获得金币。当戳破气球i时,你获得nums[i-1] × nums[i] × nums[i1]枚金币(边界视为1)。戳破后,左右两侧气球会相邻。求能获得金币的最大数量。示例:输入:nums [3,1,5,8] 输出:167 解释: 戳破1: 3 × 1 × 5 15 戳破5: 3 × 5 × 8 120 戳破3: 1 × 3 × 8 24 戳破8: 1 × 8 × 1 8 总计:15 120 24 8 167约束条件:1 ≤ nums.length ≤ 3000 ≤ nums[i] ≤ 100需要找到最优戳破顺序以获得最大金币 边界用例(面试必考)用例类型输入期望输出考察点最小输入nums[1]1单个气球两个元素nums[3,1]6 (戳1再戳3:1×1×31×3×1)顺序影响含零元素nums[0,1,0]1零值处理大规模n300—性能边界 思路引导生活化比喻想象你要拆除一排老房子,每拆一栋能获得报酬,但报酬取决于两侧邻居房的价值。笨办法:尝试所有拆除顺序(6个房子就有720种顺序),用暴力回溯穷举,时间复杂度O(n!)会爆炸。聪明办法:换个思路——不考虑先戳哪个,而是假设最后戳哪个。把问题变成区间内最后戳k号气球,左右两侧是独立子问题,用区间DP自底向上求解。关键洞察逆向思考:不是先戳哪个,而是最后戳哪个!这样左右区间互不影响,可以独立求解。 解题思维链这一节模拟你在面试中从零开始思考的过程。Step 1:理解题目 → 锁定输入输出输入:nums数组,表示气球上的数字输出:整数,能获得的最大金币数限制:戳破顺序会影响结果,边界外视为数字1Step 2:先想笨办法(暴力法)对于每个位置,尝试先戳它,然后递归处理剩余气球。时间复杂度:O(n!) — n个气球有n!种排列瓶颈在哪:戳破一个气球后,两侧气球变相邻,状态变化复杂,难以用DP表达Step 3:瓶颈分析 → 优化方向暴力法的问题是先戳导致两侧气球关系变化,无法定义清晰的子问题。核心问题:戳破顺序导致状态转移复杂优化思路:逆向思考— 假设某个气球是区间内最后戳破的,这时左右两侧气球固定,子问题独立Step 4:选择武器选用:区间DP(Interval DP)理由:逆向假设最后戳k号气球,此时i-1和j1号气球还在定义dp[i][j]为戳破区间(i, j)内所有气球(不含i和j)能获得的最大金币状态转移:dp[i][j] max(dp[i][k] nums[i]*nums[k]*nums[j] dp[k][j]),枚举k为最后戳破的气球模式识别提示:当题目涉及区间操作且顺序影响结果时,优先考虑区间DP 逆向思考 解法一:回溯穷举(直觉法)思路尝试每个位置作为下一个戳破的气球,递归计算剩余气球的最优解。(此解法仅用于理解问题,实际会超时)图解过程输入:nums [3,1,5,8] Step 1:尝试先戳3 剩余:[1,5,8] → 递归计算 Step 2:尝试先戳1 剩余:[3,5,8] → 递归计算 ...依次尝试所有顺序 问题:状态空间巨大,会TLEPython代码fromtypingimportListdefmaxCoins_backtrack(nums:List[int])-int: 解法一:回溯穷举 思路:尝试所有戳破顺序,递归计算最大值 defbacktrack(arr):ifnotarr:return0max_coins0foriinrange(len(arr)):# 戳破第i个气球leftarr[i-1]ifi0else1rightarr[i1]ifilen(arr)-1else1coinsleft*arr[i]*right# 递归处理剩余气球new_arrarr[:i]arr[i1:]max_coinsmax(max_coins,coinsbacktrack(new_arr))returnmax_coinsreturnbacktrack(nums)# ✅ 测试print(maxCoins_backtrack([3,1,5,8]))# 期望输出:167print(maxCoins_backtrack([1,5]))# 期望输出:10复杂度分析时间复杂度(n!) — 每层递归尝试n种选择,深度为n具体地说:如果n10,大约需要10! 3,628,800次操作,不可接受空间复杂度(n²) — 递归栈深度n,每层创建新数组优缺点✅ 思路直观,易于理解❌ 时间复杂度爆炸,n10就会超时,无法通过OJ 解法二:区间DP(最优解)优化思路关键洞察:逆向思考— 不考虑先戳哪个,而是假设最后戳哪个。定义dp[i][j]为戳破开区间(i, j)内所有气球能获得的最大金币(不含边界i和j)。枚举区间内每个位置k作为最后戳破的气球,此时左右两侧气球都还在,金币为nums[i]*nums[k]*nums[j]。关键想法:假设k是区间(i,j)内最后戳的,那么它左边(i,k)和右边(k,j)是独立的子问题!图解过程输入:nums [3,1,5,8] 添加虚拟边界:nums [1,3,1,5,8,1] 初始化:dp[i][j] 0 (所有区间) 区间长度len3(即包含1个真实气球)的情况: dp[0][2]: 区间(0,2)即只有气球1(值为3) 假设k1最后戳:1*3*13 dp[0][2] 3 dp[1][3]: 区间(1,3)即只有气球2(值为1) 假设k2最后戳:3*1*13 dp[1][3] 3 ... 区间长度len4(即包含2个真实气球): dp[0][3]: 区间(0,3)包含气球[3,1] k1最后戳:dp[0][1]1*3*1dp[1][3]0336 k2最后戳:dp[0][2]1*1*1dp[2][3]3104 dp[0][3] max(6,4)6 ... 最终:dp[0][5] 戳破所有气球的最大金币 167Python代码defmaxCoins(nums:List[int])-int: 解法二:区间DP(最优解) 思路:逆向假设最后戳哪个,区间DP求最大值 # 添加虚拟边界,简化边界处理nums[1]nums[1]nlen(nums)# dp[i][j] 戳破开区间(i,j)内所有气球能获得的最大金币dp[[0]*nfor_inrange(n)]# 从小区间到大区间枚举forlengthinrange(3,n1):# 区间长度至少为3(含两个虚拟边界)foriinrange(n-length1):jilength-1# 枚举区间(i,j)内最后戳破的气球kforkinrange(i1,j):# 最后戳k时,左右两侧气球i和j还在coinsdp[i][k]nums[i]*nums[k]*nums[j]dp[k][j]dp[i][j]max(dp[i][j],coins)returndp[0][n-1]# ✅ 测试print(maxCoins([3,1,5,8]))# 期望输出:167print(maxCoins([1,5]))# 期望输出:10print(maxCoins([1]))# 期望输出:1复杂度分析时间复杂度(n³) — 三层循环:区间长度O(n),起点O(n),枚举k O(n)具体地说:n300时,大约需要300³ 27,000,000次操作,在1秒内可以完成空间复杂度(n²) — DP表的大小为什么是最优解✅ 时间复杂度O(n³)是区间DP问题的理论最优解✅ 空间O(n²)合理,DP表必须存储所有子区间的结果✅ 代码清晰,符合区间DP的标准模板✅ 通过逆向思考巧妙化解了正向思考的状态转移难题 Pythonic 写法利用Python的itertools和lru_cache可以写出记忆化递归版本:fromfunctoolsimportlru_cachedefmaxCoins_memo(nums:List[int])-int:记忆化递归版本:自顶向下的区间DPnums[1]nums[1]lru_cache(None)defdp(i:int,j:int)-int:返回戳破开区间(i,j)内所有气球的最大金币ifi1j:# 区间内没有气球return0max_coins0forkinrange(i1,j):coinsdp(i,k)nums[i]*nums[k]*nums[j]dp(k,j)max_coinsmax(max_coins,coins)returnmax_coinsreturndp(0,len(nums)-1)这个写法用自顶向下的递归思路,更接近人的思维习惯,lru_cache自动处理重复子问题的缓存。⚠️面试建议:先写清晰的自底向上DP版本(解法二)展示思路,再提记忆化递归展示Python功底。面试官更看重你的DP建模能力,而非递归写法。 解法对比维度解法一:回溯穷举 解法二:区间DP(最优)时间复杂度O(n!)O(n³)← 时间最优空间复杂度O(n²)O(n²)← 相同代码难度简单(但会TLE)中等(理解逆向思考)面试推荐⭐⭐⭐⭐← 首选适用场景仅用于理解问题面试必会,通用性强为什么是最优解:时间复杂度O(n³)是区间DP的理论最优(需枚举所有区间和分割点)逆向思考最后戳哪个是破解此题的核心技巧代码结构清晰,符合区间DP标准模板面试建议:先花1分钟分析暴力回溯为什么会超时(O(n!)太大)重点讲解区间DP的核心思想:“不看先戳谁,而是假设最后戳谁”强调状态定义:dp[i][j]表示开区间(i,j)(不含i,j)内的最大金币展示状态转移:枚举k作为最后戳破的气球,dp[i][j] max(dp[i][k] nums[i]*nums[k]*nums[j] dp[k][j])提醒边界处理:添加虚拟边界[1,...,1]简化代码 面试现场模拟面试中的完整对话流程,帮你练习边想边说。面试官:请你解决一下这道题。你:(审题30秒)好的,这道题要求找到戳破气球的最优顺序,使得获得的金币最大。我的第一个想法是用回溯穷举所有戳破顺序,但这样时间复杂度是O(n!),n300时会超时。我注意到这是一个典型的区间DP问题。关键洞察是:逆向思考— 不考虑先戳哪个,而是假设某个气球是区间内最后戳破的。这样,它左右两侧的气球都还在,形成独立的子问题。我会定义dp[i][j]为戳破开区间(i,j)内所有气球(不含i和j)能获得的最大金币。状态转移是枚举区间内每个位置k作为最后戳破的气球。时间复杂度优化到O(n³)。面试官:很好,请写一下代码。你:(边写边说关键步骤)# 1. 添加虚拟边界[1,...,1],简化边界处理nums[1]nums[1]# 2. 初始化DP表dp[[0]*nfor_inrange(n)]# 3. 从小区间到大区间枚举forlengthinrange(3,n1):foriinrange(n-length1):jilength-1# 4. 枚举k作为最后戳破的气球forkinrange(i1,j):coinsdp[i][k]nums[i]*nums[k]*nums[j]dp[k][j]dp[i][j]max(dp[i][j],coins)面试官:测试一下?你:用示例[3,1,5,8]走一遍…(手动模拟小区间的DP过程)。再测一个边界情况[1],只有一个气球,输出1。结果正确。高频追问追问应答策略“为什么要逆向思考?”正向考虑先戳谁会导致两侧气球变相邻,状态转移复杂;逆向假设最后戳谁时,两侧边界固定,子问题独立“能不能O(n²)优化?”不能,必须枚举所有区间(O(n²))和每个区间内的分割点(O(n)),最优就是O(n³)“为什么添加虚拟边界?”简化边界处理,避免判断i-1和j1是否越界,代码更简洁“这题和矩阵链乘法有什么关系?”都是区间DP,状态转移都是枚举分割点k,模式相同 知识点总结Python技巧卡片 # 技巧1:添加虚拟边界简化边界判断nums[1]nums[1]# 在首尾添加1# 技巧2:记忆化递归的装饰器写法fromfunctoolsimportlru_cachelru_cache(None)defdp(i,j):# 递归函数,自动缓存结果pass# 技巧3:三层循环枚举区间forlengthinrange(3,n1):# 区间长度foriinrange(n-length1):# 起点jilength-1# 终点forkinrange(i1,j):# 分割点# 状态转移 底层原理(选读)区间DP的核心思想:子问题定义:通常定义为dp[i][j]表示区间[i,j]或(i,j)的最优解状态转移:枚举区间内的分割点k,将大区间拆成两个小区间枚举顺序:从小区间到大区间(长度从小到大),保证计算大区间时小区间已求解逆向思考技巧:当正向顺序导致状态复杂时,尝试最后做什么的逆向分析本题的巧妙之处:正向思考先戳谁会导致两侧气球关系变化,无法定义清晰的子问题逆向思考最后戳谁时,左右边界固定,子问题独立且可以合并算法模式卡片 模式名称:区间DP(Interval DP)适用条件:问题涉及对一段连续区间的操作大问题可以通过分割成小区间求解操作顺序影响结果,需要枚举所有可能识别关键词:“戳气球”、“合并石子”、“括号匹配”“区间操作”、“最优分割”题目要求最优化(最大/最小)某个区间操作结果模板代码:definterval_dp(nums):nlen(nums)dp[[0]*nfor_inrange(n)]# 从小区间到大区间枚举forlengthinrange(1,n1):foriinrange(n-length1):jilength-1# 枚举分割点kforkinrange(i,j1):dp[i][j]max(dp[i][j],dp[i][k]dp[k1][j]cost(i,k,j))returndp[0][n-1]易错点 ⚠️状态定义错误:❌ 错误:定义dp[i][j]为闭区间[i,j]的最大金币✅ 正确:定义为开区间(i,j)(不含边界),边界需要保留作为两侧气球原因:假设k是最后戳的,需要nums[i]*nums[k]*nums[j],边界i和j必须保留区间枚举顺序错误:❌ 错误:从大区间到小区间枚举,或从左到右枚举起点✅ 正确:必须从小区间到大区间(长度从小到大),保证计算大区间时依赖的小区间已计算原因:区间DP有依赖关系,dp[i][j]依赖于更小的dp[i][k]和dp[k][j]忘记添加虚拟边界:❌ 错误:直接用原数组,需要大量if判断越界✅ 正确:在首尾添加虚拟边界[1],简化代码原因:边界气球视为1,添加虚拟边界后无需特殊判断️ 工程实战(选读)这个算法思想在真实项目中的应用,让你知道学了有什么用。场景1:任务调度优化 — 在工厂生产线上,多个工序有依赖关系,求最优执行顺序使得总成本最小,可以用区间DP建模场景2:DNA序列对齐 — 生物信息学中,对齐两个DNA序列找到最优匹配方式,涉及插入/删除/替换操作的最优化,与区间DP思想类似场景3:矩阵链乘法优化 — 数据库查询优化器决定多表连接的顺序,使得总计算量最小,经典的区间DP问题️ 举一反三完成本课后,试试这些同类题目来巩固知识:题目难度相关知识点提示LeetCode 1039. 多边形三角剖分的最低得分Medium区间DP枚举三角形的第三个顶点作为分割点LeetCode 375. 猜数字大小IIMedium区间DP枚举猜哪个数字,求最坏情况下的最小成本LeetCode 1000. 合并石子的最低成本Hard区间DP 前缀和枚举合并点k,需要前缀和优化区间和计算LeetCode 96. 不同的二叉搜索树Medium区间DP(变体)枚举根节点,左右子树是独立子问题 课后小测试试这道变体题,不要看答案,自己先想5分钟!题目:给定一个字符串,你可以在任意位置插入括号,使得最终的表达式计算结果最大。字符串只包含数字和运算符、-、*。例如2*3-4*5可以变为2*(3-(4*5)),求最大值。 提示(实在想不出来再点开)用区间DP,定义dp[i][j]为区间[i,j]的最大值和最小值(需要同时维护,因为负负得正)。枚举运算符位置k作为分割点。✅ 参考答案defmaxValue(s:str)-int: 区间DP:同时维护最大值和最小值 nlen(s)# 分离数字和运算符nums[]ops[]num0forchins:ifch.isdigit():numnum*10int(ch)else:nums.append(num)ops.append(ch)num0nums.append(num)mlen(nums)# dp_max[i][j] 区间[i,j]的最大值# dp_min[i][j] 区间[i,j]的最小值dp_max[[float(-inf)]*mfor_inrange(m)]dp_min[[float(inf)]*mfor_inrange(m)]# 初始化:单个数字foriinrange(m):dp_max[i][i]nums[i]dp_min[i][i]nums[i]# 从小区间到大区间枚举forlengthinrange(2,m1):foriinrange(m-length1):jilength-1# 枚举分割点k(运算符位置)forkinrange(i,j):opops[k]# 左右两侧的最大最小值left_max,left_mindp_max[i][k],dp_min[i][k]right_max,right_mindp_max[k1][j],dp_min[k1][j]# 根据运算符计算可能的值ifop:vals[left_maxright_max]elifop-:vals[left_max-right_min]else:# *vals[left_max*right_max,left_max*right_min,left_min*right_max,left_min*right_min]dp_max[i][j]max(dp_max[i][j],max(vals))dp_min[i][j]min(dp_min[i][j],min(vals))returndp_max[0][m-1]核心思路:与戳气球类似,枚举运算符作为分割点,但需要同时维护最大最小值(因为负负得正)。如果这篇内容对你有帮助推荐收藏 AI Compasshttps://github.com/tingaicompass/AI-Compass更多系统化题解、编程基础和 AI 学习资料都在这里后续复习和拓展会更省时间。