企业官网建设流程全解析

LeetCode 638 大礼包（Shopping Offers）

难度：Medium
标签：回溯、记忆化搜索、DFS、剪枝

题目原文

在 LeetCode 商店中，有 n 件商品正在出售，每件商品都有一个价格。商店提供一些大礼包优惠。

给定：

1. price：长度为n的数组，price[i]代表第i件物品单独购买的单价。
2. special：大礼包数组。special[i]长度是 n+1；前n个数字代表礼包内每种物品的数量，最后一个数字是这个礼包售价。
3. needs：购物清单数组，needs[i]代表你恰好要买第i件物品多少个。

规则：

1. 大礼包可以无限次购买；
2. 购买礼包/单品之后，任意物品总数不能超过needs里的数量，哪怕多买一点能省钱，也不允许；
3. 目标：刚好凑齐needs清单，求最低花费。

示例1

price = [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个，单独买：22=4；合计14。
直接单独买全部：32 +2*5=16，更贵。

示例2

price = [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

1. 先算：如果不再买礼包，全部单独买，需要多少钱 → 作为当前最小值min_cost
2. 遍历每一个礼包：
   • 判断礼包内物品数量，是否全部 ≤ curr_needs（不能买超）
   • 如果可以买：生成新的需求清单（减去礼包里物品），递归求新清单最低价格
   • 当前花费 = 礼包价格 + 递归返回的剩余物品最低价
   • 更新min_cost
3. 返回min_cost

❌ 问题：不同递归分支，会遇到完全一样的needs数组，重复计算，浪费大量时间。

例如两条不同礼包选择路径，最后剩下的购物清单都是[2,1]，朴素DFS会重新算一遍[2,1]的最小花费。

✅ 优化：记忆化（备忘录memo）
把needs元组当作key，把这个需求对应的最小价格存起来；下次遇到同样需求直接查表，不再递归。

数组不能做字典key，转元组tuple存进memo。

额外重要剪枝（面试必写）

礼包有可能定价坑人：礼包总价 ≥ 单独买礼包里面物品的总价，这种礼包永远不要选，预处理直接删掉，减少递归分支。
例：礼包 [1,1,10]，两件单品总价 2+5=7，礼包卖10，比单独买还贵，直接丢弃这个礼包。

第三步：边界条件

1. needs全部为0：不需要买任何东西，花费=0；
2. 没有可用礼包：直接全部单独买单件；
3. 任何礼包物品数量超过当前needs，不能选。

第四步：算法对比

1. 纯暴力DFS：不记忆，大量重复计算，小数据勉强能跑，数据稍微大一点超时；
2. DFS + 记忆化（推荐，本题最优）：状态很少！n最多6，每个物品最多10，状态总数不大，非常适合；
3. DP：可以写，但状态编码麻烦；记忆化递归写起来最简单直观。

现实应用场景举例

1. 电商促销系统：多种套餐、满减组合，计算满足用户固定购物清单最低花费；
2. 原材料采购：供应商提供单品价格+组合打包套餐，采购固定数量物料，求最低采购成本；
3. 游戏礼包系统：游戏商店，角色需要固定数量材料，礼包可重复购买，计算最优购买方案。

Python代码：记忆化DFS（带逐行详细注释）

fromtypingimportListfromfunctoolsimportlru_cacheclassSolution:defshoppingOffers(self,price:List[int],special:List[List[int]],needs:List[int])->int:# 物品总数量nn=len(price)# ==========预处理礼包：过滤掉不划算的礼包，减少递归分支==========valid_special=[]forbundleinspecial:# bundle最后一位是礼包价格，前面n位是物品数量bundle_cost=bundle[-1]single_total=0is_valid=Trueforiinrange(n):cnt=bundle[i]# 礼包物品数量不能负数（题目保证，这里做保护）ifcnt<0:is_valid=Falsebreak# 计算礼包内物品单独买的总价single_total+=cnt*price[i]# 剪枝条件：礼包价格 < 单独买礼包内物品的价格，这个礼包才值得保留ifis_validandbundle_cost<single_total:valid_special.append(bundle)# 将needs转为元组，因为list不能被lru_cache缓存，tuple可以哈希# 定义递归函数，参数是当前还需要购买的物品数量元组@lru_cache(maxsize=None)defdfs(curr_needs_tuple):# 方案1：不买任何礼包，全部单独购买，算出基础价格total=0foriinrange(n):total+=curr_needs_tuple[i]*price[i]# min_cost初始化为全部单买的价格min_cost=total# 遍历每一个有效的礼包forbundleinvalid_special:# 标记当前礼包是否可以购买：礼包每种物品数量不能超过当前需要can_buy=Truenew_needs=list(curr_needs_tuple)foriinrange(n):bundle_item_cnt=bundle[i]# 如果礼包该物品数量 > 当前还需要的数量，不能买这个礼包ifbundle_item_cnt>new_needs[i]:can_buy=Falsebreak# 购买礼包，减去礼包内物品数量new_needs[i]-=bundle_item_cnt# 如果这个礼包可以购买ifcan_buy:# 递归：购买这个礼包后，剩下物品的最小花费# new_needs转tuple传入dfsrest_cost=dfs(tuple(new_needs))# 当前方案总花费：礼包价格 + 剩余物品最小花费current_cost=bundle[-1]+rest_cost# 更新全局最小花费ifcurrent_cost<min_cost:min_cost=current_cost# 返回当前需求对应的最小花费returnmin_cost# 初始调用：把needs列表转为元组传入dfsreturndfs(tuple(needs))# ========== 测试样例 ==========if__name__=="__main__":sol=Solution()# 样例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

代码关键点费曼复盘

1. lru_cache只能缓存可哈希类型，列表list不行，必须转tuple；
2. 预处理礼包是非常重要的剪枝：礼包比单独买还贵，直接丢掉，减少递归；
3. 每次递归第一步，先算全部单买的价格，作为保底最小值，就算所有礼包都不划算，也能返回正确值；
4. 递归遍历礼包，只要礼包物品数量不超过当前需求，就尝试购买，递归求剩余的最小值；
5. 状态数量有限：n最多6，每种物品最多10，总状态很小，记忆化效率极高。

复杂度分析

状态数：每个物品最多0~10，最多6件物品，总状态不超过116=177156111^6=1771561116=1771561，实际经过剪枝远小于这个数。
每个状态遍历所有礼包，本题数据完全可以通过。

补充：纯暴力无记忆DFS版本（理解用，不推荐面试写）

fromtypingimportListclassSolution:defshoppingOffers(self,price:List[int],special:List[List[int]],needs:List[int])->int:n=len(price)# 预处理筛选划算礼包valid_special=[]forbundleinspecial:sum_single=sum(bundle[i]*price[i]foriinrange(n))ifbundle[-1]<sum_single:valid_special.append(bundle)defdfs(curr_needs):# 全部单买价格cost=sum(curr_needs[i]*price[i]foriinrange(n))min_cost=costforbundleinvalid_special:ok=Truenew_need=curr_needs.copy()foriinrange(n):ifbundle[i]>new_need[i]:ok=Falsebreaknew_need[i]-=bundle[i]ifok:new_cost=bundle[-1]+dfs(new_need)min_cost=min(min_cost,new_cost)returnmin_costreturndfs(needs)

缺点：大量重复子问题，当needs数组偏大时会超时，只适合理解递归逻辑。