题目描述
思路解析
一句话答案：买齐购物清单、可用打包礼包，求最低总花费，就是 LeetCode 638 大礼包。状态设成还需向量，先按原价单买兜底，再逐个试不超需的礼包递归取最小并记忆化，时间 O(状态数×礼包数×n)、空间 O(状态数)。
大礼包这道题，买齐清单最少花多少钱
每件商品有原价，另有几种大礼包，每个礼包打包几件给一个打包价，可无限次买。清单 needs 写明每件要买几个，求买齐的最低花费，且每件买到手都不能超过清单。price=[2,5]、礼包 [3 个 A 价 5] 和 [1 个 A 加 2 个 B 价 10]、needs=[3,2]，原价单买 16，巧用礼包压到 14。
为什么贪心挑最便宜的礼包会算错
贪心最顺手，每步挑当下最划算的礼包，但会挑反：某礼包眼下最省，买下去却让剩下凑不成别的组合，反倒更贵。想稳妥就把所有买法试一遍，一路分叉；可礼包一多、清单一长买法就成倍翻、试不完，更糟的是同一个『还差多少没买』的局面会被反复重算。
状态设成『还差多少没买』，答案怎么拆
不纠结先买哪个后买哪个，只盯一件事：现在还差多少没买，写成一个还需向量，还要 3 个 A、2 个 B 就记成 [3,2]。任何买法走到某步，只要剩下还需相同，后面怎么买最省就一样，和之前买过什么、什么顺序都无关。
定义 dfs(还需向量) 为从这个局面买齐的最低花费。dfs 就是一个自己调用自己的函数（递归），拿它当键把结果存下来，这就是记忆化搜索（算过的局面存进表，再遇到直接取值）。
礼包买不买，为什么取 min 就对
算 dfs(还需) 从两种来路取小。第一种是原价单买，剩下每件按原价乘还需加起来，是不用礼包的兜底价，先当当前最优；有时所有礼包都不划算，这条退路必须留。
第二种是逐个试礼包，能不能买只看一条：礼包每件要拿的数量都不超过对应还需，有一件超了就超买，题目不许，直接跳过。买得起就扣掉礼包数量得到新还需，花费 = 礼包价 + dfs(新还需)，和当前最优比谁小留谁。能不能买只管超不超买，划不划算交给取小裁。
拿 needs=[3,2] 这组示例手工走一遍
顶层 dfs([3,2])：原价单买是 2×3+5×2=16，先记 16。试礼包1[3 个 A]：A 3≥3、B 2≥0 买得起，扣成 [0,2]，花费 5+dfs([0,2])；dfs([0,2]) 里 A 已是 0、两礼包都要 A 拿不出，只能原价买 2 个 B 得 10，即 5+10=15 比 16 省。
再试礼包2[1 个 A 加 2 个 B]：A 3≥1、B 2≥2 买得起，扣成 [2,0]，花费 10+dfs([2,0])；dfs([2,0]) 里 B 已是 0，礼包2 要 2 个 B 超买、礼包1 要 3 个 A 也不够，只能原价买 2 个 A 得 4，即 10+4=14 比 15 更省。dfs([3,2]) 取小得 14 就是答案。
状态数为什么不会爆，超买和兜底别漏
状态数是关键账：每件还需只能从 0 到清单上限，各件（还需+1）连乘即上限，『不能超买』死死压住它，本例只走出 [3,2]、[0,2]、[2,0] 三个。每状态遍历礼包各 n 件，记忆化只算一次，时间 O(状态数×礼包数×n)。漏了原价单买这条兜底最要命，所有礼包都不划算时就彻底没退路。漏判超买同样致命：礼包数量超过还需会让还需变负，整个答案跟着错。清单为空花费 0、无礼包时全按原价单买，边界都自动对。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心一句话:状态是「还需向量」,答案 = min(原价单买, 每个买得起的礼包价 + 递归剩余)。算过就记下来。
先把输入摆上台:要买 3 个 A、2 个 B,写成状态 [3,2]。右边面板是备忘录,现在空着。下面从顶层 dfs([3,2]) 开始递归。
进入第一层 dfs([3,2])。按套路,第一步永远先算不用任何礼包的原价兜底,心里有个底再去试礼包。
原价单买 3 个 A、2 个 B 共 16 元,先把当前最优 ans 记成 16。礼包只是可选项,这个 16 必须先占着位置。
试礼包1:每件拿的数量都不超过当前还需,买得起。能不能买只看会不会超买,划不划算交给后面取最小。
买下礼包1,扣掉 3 个 A,清单从 [3,2] 变成 [0,2],先付礼包价 5 元,剩下的 [0,2] 丢给下一层递归。
进入第二层 dfs([0,2]):A 不用买了,只要凑齐 2 个 B。流程照旧,先算原价兜底再逐个试礼包。
这层原价兜底:A 要 0 个不花钱,B 要 2 个共 10 元。先把这层 ans 记成 10,再看礼包能不能帮上忙。
试礼包1,它要 3 个 A,可现在 A 的还需已是 0,拿不出 3 个,一买就超买,买不起,直接跳过。
再试礼包2,它要 1 个 A,A 的还需仍是 0,连 1 个都拿不出,同样超买。礼包2 也买不起。
dfs([0,2]) 两个礼包都买不起,只能用兜底 10 元。把状态 [0,2] 对应 10 元记进备忘录,返回上一层。
结果回到 dfs([3,2])。走礼包1 这条路 = 礼包价 5 + 子状态 [0,2] 的 10 = 15 元,比 16 省,ans 更新成 15。
试礼包2:还需 A=3≥1、还需 B=2≥2,两件都不超买,正好都够,礼包2 买得起。
买下礼包2,扣掉 1 个 A、2 个 B,清单从 [3,2] 变成 [2,0],先付 10 元,剩下的 [2,0] 丢给下一层。
进入 dfs([2,0]),只要凑齐 2 个 A。套路照旧,先兜底再试礼包,这次走快一点。
原价兜底:2 个 A 每个 2 元共 4 元,B 不用买。这层 ans 先记成 4。
礼包1 要 3 个 A,可手上只还需 2 个 A,凑不够 3,买了就超清单,买不起。
礼包2 要 2 个 B,而 B 的还需已是 0,一个都不能再买,这回卡在 B 上,也买不起。
两个礼包又都落空,dfs([2,0]) 用兜底 4 元。把 [2,0] 对应 4 元记进备忘录,返回上一层。备忘录攒到两条。
回到 dfs([3,2])。走礼包2 这条路 = 礼包价 10 + 子状态 [2,0] 的 4 = 14 元,比 15 省,ans 更新成 14。
dfs([3,2]) 能试的礼包全试过,最低花费锁定 14 元。把顶层状态 [3,2] 对应 14 记进备忘录,返回主程序。三个状态全算完。
回看备忘录三条记录都在。本例每个状态只出现一次,但商品、礼包一多,同一剩余状态会被反复递归到,那时直接取值,这正是记忆化的价值。
最优买法:花 10 元买礼包2 拿到 1A2B,剩下 2 个 A 原价单买 4 元,合计 14 元,比原价单买的 16 元省了 2 元。
边界先想清:无礼包退化成原价、清单为空花 0、坑爹礼包会被 min 自动丢弃。
两个高频追问:为什么不能贪心、以及位掩码编码的用意。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def shoppingOffers( self, price: List[int], special: List[List[int]], needs: List[int] ) -> int: @cache def dfs(cur: int) -> int: ans = sum(p * (cur >> (i * bits) & 0xF) for i, p in enumerate(price)) for offer in special: nxt = cur for j in range(len(needs)): if (cur >> (j * bits) & 0xF) < offer[j]: break nxt -= offer[j] << (j * bits) else: ans = min(ans, offer[-1] + dfs(nxt)) return ans bits, mask = 4, 0 for i, need in enumerate(needs): mask |= need << i * bits return dfs(mask)复杂度
- 时间：O(状态数 × 礼包数 × n)，状态最多 ∏(needs[i]+1) 个,每个状态遍历所有礼包、每礼包查 n 件
- 空间：O(状态数)，备忘录给每个出现过的还需向量存一条;递归栈深度不超过总购买次数
易错点
面试追问把动画讲成自己的话
追问为什么这题用记忆化搜索而不是直接贪心选最便宜的礼包?
追问参考代码为什么把还需向量压成一个整数?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长数对链
LeetCode 646 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题