大礼包

核心一句话:状态是「还需向量」,答案 = 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 自动丢弃。

两个高频追问:为什么不能贪心、以及位掩码编码的用意。