LeetCode 638 大礼包Shopping Offers难度Medium标签回溯、记忆化搜索、DFS、剪枝题目原文在 LeetCode 商店中有 n 件商品正在出售每件商品都有一个价格。商店提供一些大礼包优惠。给定price长度为n的数组price[i]代表第i件物品单独购买的单价。special大礼包数组。special[i]长度是 n1前n个数字代表礼包内每种物品的数量最后一个数字是这个礼包售价。needs购物清单数组needs[i]代表你恰好要买第i件物品多少个。规则大礼包可以无限次购买购买礼包/单品之后任意物品总数不能超过needs里的数量哪怕多买一点能省钱也不允许目标刚好凑齐needs清单求最低花费。示例1price [2,5] special [[3,0,5],[1,2,10]] needs [3,2] 输出14解释物品0单价2物品1单价5。方案买一次礼包[1,2,10]得到物品0:1物品1:2花费10剩下物品0还缺2个单独买224合计14。直接单独买全部32 2*516更贵。示例2price [2,3,4] special [[1,1,0,4],[2,2,1,9]] needs [1,2,1] 输出11提示n 取值范围1 n 6每种物品需要数量0 needs[i] 10礼包内物品数量都是非负整数礼包价格0费曼学习法拆解用大白话讲给小白第一步读懂问题翻译成生活例子想象超市购物商品A、B、C各自标价有多种组合礼包礼包打包卖可能更便宜你有固定购物清单每种东西不能多买礼包可以反复买问怎么搭配礼包单独购买刚好买够清单里的数量花钱最少。核心这是一个组合选择问题。每一步我们有两个大类选择① 选一个可用礼包礼包里每种物品数量 ≤ 当前还需要的数量买这个礼包更新购物清单递归继续算剩下物品的最低价格② 不再买任何礼包剩下物品全部单独买单件算出总价。所有方案取最小值。第二步识别暴力解法的缺陷引出记忆化朴素回溯无记忆递归思路当前需求清单curr_needs先算如果不再买礼包全部单独买需要多少钱 → 作为当前最小值min_cost遍历每一个礼包判断礼包内物品数量是否全部 ≤ curr_needs不能买超如果可以买生成新的需求清单减去礼包里物品递归求新清单最低价格当前花费 礼包价格 递归返回的剩余物品最低价更新min_cost返回min_cost❌ 问题不同递归分支会遇到完全一样的needs数组重复计算浪费大量时间。例如两条不同礼包选择路径最后剩下的购物清单都是[2,1]朴素DFS会重新算一遍[2,1]的最小花费。✅ 优化记忆化备忘录memo把needs元组当作key把这个需求对应的最小价格存起来下次遇到同样需求直接查表不再递归。数组不能做字典key转元组tuple存进memo。额外重要剪枝面试必写礼包有可能定价坑人礼包总价 ≥ 单独买礼包里面物品的总价这种礼包永远不要选预处理直接删掉减少递归分支。例礼包 [1,1,10]两件单品总价 257礼包卖10比单独买还贵直接丢弃这个礼包。第三步边界条件needs全部为0不需要买任何东西花费0没有可用礼包直接全部单独买单件任何礼包物品数量超过当前needs不能选。第四步算法对比纯暴力DFS不记忆大量重复计算小数据勉强能跑数据稍微大一点超时DFS 记忆化推荐本题最优状态很少n最多6每个物品最多10状态总数不大非常适合DP可以写但状态编码麻烦记忆化递归写起来最简单直观。现实应用场景举例电商促销系统多种套餐、满减组合计算满足用户固定购物清单最低花费原材料采购供应商提供单品价格组合打包套餐采购固定数量物料求最低采购成本游戏礼包系统游戏商店角色需要固定数量材料礼包可重复购买计算最优购买方案。Python代码记忆化DFS带逐行详细注释fromtypingimportListfromfunctoolsimportlru_cacheclassSolution:defshoppingOffers(self,price:List[int],special:List[List[int]],needs:List[int])-int:# 物品总数量nnlen(price)# 预处理礼包过滤掉不划算的礼包减少递归分支valid_special[]forbundleinspecial:# bundle最后一位是礼包价格前面n位是物品数量bundle_costbundle[-1]single_total0is_validTrueforiinrange(n):cntbundle[i]# 礼包物品数量不能负数题目保证这里做保护ifcnt0:is_validFalsebreak# 计算礼包内物品单独买的总价single_totalcnt*price[i]# 剪枝条件礼包价格 单独买礼包内物品的价格这个礼包才值得保留ifis_validandbundle_costsingle_total:valid_special.append(bundle)# 将needs转为元组因为list不能被lru_cache缓存tuple可以哈希# 定义递归函数参数是当前还需要购买的物品数量元组lru_cache(maxsizeNone)defdfs(curr_needs_tuple):# 方案1不买任何礼包全部单独购买算出基础价格total0foriinrange(n):totalcurr_needs_tuple[i]*price[i]# min_cost初始化为全部单买的价格min_costtotal# 遍历每一个有效的礼包forbundleinvalid_special:# 标记当前礼包是否可以购买礼包每种物品数量不能超过当前需要can_buyTruenew_needslist(curr_needs_tuple)foriinrange(n):bundle_item_cntbundle[i]# 如果礼包该物品数量 当前还需要的数量不能买这个礼包ifbundle_item_cntnew_needs[i]:can_buyFalsebreak# 购买礼包减去礼包内物品数量new_needs[i]-bundle_item_cnt# 如果这个礼包可以购买ifcan_buy:# 递归购买这个礼包后剩下物品的最小花费# new_needs转tuple传入dfsrest_costdfs(tuple(new_needs))# 当前方案总花费礼包价格 剩余物品最小花费current_costbundle[-1]rest_cost# 更新全局最小花费ifcurrent_costmin_cost:min_costcurrent_cost# 返回当前需求对应的最小花费returnmin_cost# 初始调用把needs列表转为元组传入dfsreturndfs(tuple(needs))# 测试样例 if__name____main__:solSolution()# 样例1price1[2,5]special1[[3,0,5],[1,2,10]]needs1[3,2]print(sol.shoppingOffers(price1,special1,needs1))# 预期输出14# 样例2price2[2,3,4]special2[[1,1,0,4],[2,2,1,9]]needs2[1,2,1]print(sol.shoppingOffers(price2,special2,needs2))#预期输出11代码关键点费曼复盘lru_cache只能缓存可哈希类型列表list不行必须转tuple预处理礼包是非常重要的剪枝礼包比单独买还贵直接丢掉减少递归每次递归第一步先算全部单买的价格作为保底最小值就算所有礼包都不划算也能返回正确值递归遍历礼包只要礼包物品数量不超过当前需求就尝试购买递归求剩余的最小值状态数量有限n最多6每种物品最多10总状态很小记忆化效率极高。复杂度分析状态数每个物品最多0~10最多6件物品总状态不超过116177156111^617715611161771561实际经过剪枝远小于这个数。每个状态遍历所有礼包本题数据完全可以通过。补充纯暴力无记忆DFS版本理解用不推荐面试写fromtypingimportListclassSolution:defshoppingOffers(self,price:List[int],special:List[List[int]],needs:List[int])-int:nlen(price)# 预处理筛选划算礼包valid_special[]forbundleinspecial:sum_singlesum(bundle[i]*price[i]foriinrange(n))ifbundle[-1]sum_single:valid_special.append(bundle)defdfs(curr_needs):# 全部单买价格costsum(curr_needs[i]*price[i]foriinrange(n))min_costcostforbundleinvalid_special:okTruenew_needcurr_needs.copy()foriinrange(n):ifbundle[i]new_need[i]:okFalsebreaknew_need[i]-bundle[i]ifok:new_costbundle[-1]dfs(new_need)min_costmin(min_cost,new_cost)returnmin_costreturndfs(needs)缺点大量重复子问题当needs数组偏大时会超时只适合理解递归逻辑。 
长河君 · 2026/10/1 16:15:57 · 阅读 1.2k LeetCode 638 大礼包
LeetCode 638 大礼包Shopping Offers难度Medium标签回溯、记忆化搜索、DFS、剪枝题目原文在 LeetCode 商店中有 n 件商品正在出售每件商品都有一个价格。商店提供一些大礼包优惠。给定price长度为n的数组price[i]代表第i件物品单独购买的单价。special大礼包数组。special[i]长度是 n1前n个数字代表礼包内每种物品的数量最后一个数字是这个礼包售价。needs购物清单数组needs[i]代表你恰好要买第i件物品多少个。规则大礼包可以无限次购买购买礼包/单品之后任意物品总数不能超过needs里的数量哪怕多买一点能省钱也不允许目标刚好凑齐needs清单求最低花费。示例1price [2,5] special [[3,0,5],[1,2,10]] needs [3,2] 输出14解释物品0单价2物品1单价5。方案买一次礼包[1,2,10]得到物品0:1物品1:2花费10剩下物品0还缺2个单独买224合计14。直接单独买全部32 2*516更贵。示例2price [2,3,4] special [[1,1,0,4],[2,2,1,9]] needs [1,2,1] 输出11提示n 取值范围1 n 6每种物品需要数量0 needs[i] 10礼包内物品数量都是非负整数礼包价格0费曼学习法拆解用大白话讲给小白第一步读懂问题翻译成生活例子想象超市购物商品A、B、C各自标价有多种组合礼包礼包打包卖可能更便宜你有固定购物清单每种东西不能多买礼包可以反复买问怎么搭配礼包单独购买刚好买够清单里的数量花钱最少。核心这是一个组合选择问题。每一步我们有两个大类选择① 选一个可用礼包礼包里每种物品数量 ≤ 当前还需要的数量买这个礼包更新购物清单递归继续算剩下物品的最低价格② 不再买任何礼包剩下物品全部单独买单件算出总价。所有方案取最小值。第二步识别暴力解法的缺陷引出记忆化朴素回溯无记忆递归思路当前需求清单curr_needs先算如果不再买礼包全部单独买需要多少钱 → 作为当前最小值min_cost遍历每一个礼包判断礼包内物品数量是否全部 ≤ curr_needs不能买超如果可以买生成新的需求清单减去礼包里物品递归求新清单最低价格当前花费 礼包价格 递归返回的剩余物品最低价更新min_cost返回min_cost❌ 问题不同递归分支会遇到完全一样的needs数组重复计算浪费大量时间。例如两条不同礼包选择路径最后剩下的购物清单都是[2,1]朴素DFS会重新算一遍[2,1]的最小花费。✅ 优化记忆化备忘录memo把needs元组当作key把这个需求对应的最小价格存起来下次遇到同样需求直接查表不再递归。数组不能做字典key转元组tuple存进memo。额外重要剪枝面试必写礼包有可能定价坑人礼包总价 ≥ 单独买礼包里面物品的总价这种礼包永远不要选预处理直接删掉减少递归分支。例礼包 [1,1,10]两件单品总价 257礼包卖10比单独买还贵直接丢弃这个礼包。第三步边界条件needs全部为0不需要买任何东西花费0没有可用礼包直接全部单独买单件任何礼包物品数量超过当前needs不能选。第四步算法对比纯暴力DFS不记忆大量重复计算小数据勉强能跑数据稍微大一点超时DFS 记忆化推荐本题最优状态很少n最多6每个物品最多10状态总数不大非常适合DP可以写但状态编码麻烦记忆化递归写起来最简单直观。现实应用场景举例电商促销系统多种套餐、满减组合计算满足用户固定购物清单最低花费原材料采购供应商提供单品价格组合打包套餐采购固定数量物料求最低采购成本游戏礼包系统游戏商店角色需要固定数量材料礼包可重复购买计算最优购买方案。Python代码记忆化DFS带逐行详细注释fromtypingimportListfromfunctoolsimportlru_cacheclassSolution:defshoppingOffers(self,price:List[int],special:List[List[int]],needs:List[int])-int:# 物品总数量nnlen(price)# 预处理礼包过滤掉不划算的礼包减少递归分支valid_special[]forbundleinspecial:# bundle最后一位是礼包价格前面n位是物品数量bundle_costbundle[-1]single_total0is_validTrueforiinrange(n):cntbundle[i]# 礼包物品数量不能负数题目保证这里做保护ifcnt0:is_validFalsebreak# 计算礼包内物品单独买的总价single_totalcnt*price[i]# 剪枝条件礼包价格 单独买礼包内物品的价格这个礼包才值得保留ifis_validandbundle_costsingle_total:valid_special.append(bundle)# 将needs转为元组因为list不能被lru_cache缓存tuple可以哈希# 定义递归函数参数是当前还需要购买的物品数量元组lru_cache(maxsizeNone)defdfs(curr_needs_tuple):# 方案1不买任何礼包全部单独购买算出基础价格total0foriinrange(n):totalcurr_needs_tuple[i]*price[i]# min_cost初始化为全部单买的价格min_costtotal# 遍历每一个有效的礼包forbundleinvalid_special:# 标记当前礼包是否可以购买礼包每种物品数量不能超过当前需要can_buyTruenew_needslist(curr_needs_tuple)foriinrange(n):bundle_item_cntbundle[i]# 如果礼包该物品数量 当前还需要的数量不能买这个礼包ifbundle_item_cntnew_needs[i]:can_buyFalsebreak# 购买礼包减去礼包内物品数量new_needs[i]-bundle_item_cnt# 如果这个礼包可以购买ifcan_buy:# 递归购买这个礼包后剩下物品的最小花费# new_needs转tuple传入dfsrest_costdfs(tuple(new_needs))# 当前方案总花费礼包价格 剩余物品最小花费current_costbundle[-1]rest_cost# 更新全局最小花费ifcurrent_costmin_cost:min_costcurrent_cost# 返回当前需求对应的最小花费returnmin_cost# 初始调用把needs列表转为元组传入dfsreturndfs(tuple(needs))# 测试样例 if__name____main__:solSolution()# 样例1price1[2,5]special1[[3,0,5],[1,2,10]]needs1[3,2]print(sol.shoppingOffers(price1,special1,needs1))# 预期输出14# 样例2price2[2,3,4]special2[[1,1,0,4],[2,2,1,9]]needs2[1,2,1]print(sol.shoppingOffers(price2,special2,needs2))#预期输出11代码关键点费曼复盘lru_cache只能缓存可哈希类型列表list不行必须转tuple预处理礼包是非常重要的剪枝礼包比单独买还贵直接丢掉减少递归每次递归第一步先算全部单买的价格作为保底最小值就算所有礼包都不划算也能返回正确值递归遍历礼包只要礼包物品数量不超过当前需求就尝试购买递归求剩余的最小值状态数量有限n最多6每种物品最多10总状态很小记忆化效率极高。复杂度分析状态数每个物品最多0~10最多6件物品总状态不超过116177156111^617715611161771561实际经过剪枝远小于这个数。每个状态遍历所有礼包本题数据完全可以通过。补充纯暴力无记忆DFS版本理解用不推荐面试写fromtypingimportListclassSolution:defshoppingOffers(self,price:List[int],special:List[List[int]],needs:List[int])-int:nlen(price)# 预处理筛选划算礼包valid_special[]forbundleinspecial:sum_singlesum(bundle[i]*price[i]foriinrange(n))ifbundle[-1]sum_single:valid_special.append(bundle)defdfs(curr_needs):# 全部单买价格costsum(curr_needs[i]*price[i]foriinrange(n))min_costcostforbundleinvalid_special:okTruenew_needcurr_needs.copy()foriinrange(n):ifbundle[i]new_need[i]:okFalsebreaknew_need[i]-bundle[i]ifok:new_costbundle[-1]dfs(new_need)min_costmin(min_cost,new_cost)returnmin_costreturndfs(needs)缺点大量重复子问题当needs数组偏大时会超时只适合理解递归逻辑。