LeetCode大礼包算法题精解：DFS记忆化搜索解决购物优惠问题

在技术招聘中，关于“潜力”与“即战力”的讨论常引发思考。一个普遍的现象是，当真正技术扎实、能立即解决复杂问题的候选人出现时，企业有时反而会因年龄等非技术因素犹豫。从本质上讲，能为业务带来确定性的问题解决能力，本身就是一种高价值。

这种在多种方案中寻找最优解的权衡思维，不仅体现在团队构建上，也是解决许多算法问题的核心。例如下面这道LeetCode上的“大礼包”问题，就需要我们系统性地在单买与组合购买之间做出最优决策。

算法题：大礼包

这道题名为「大礼包」，场景源于常见的购物优惠：在指定商品和需求下，如何混合使用单价与优惠礼包，以达到总花费最低的目标。

问题解析

题目可以概括为：

• 有 n 种商品，每种有一个单价 price[i]。
• 提供若干个「大礼包」 special[j]，每个礼包描述了购买固定数量组合的商品所需的总价。
• 给定一个最终购买需求 needs[i]，求满足此需求的最小花费。
• 重要限制：不允许超量购买（即不能为了用礼包而购买多余的商品）。

这实际上是一个在约束条件下的组合优化问题。其解题思路与数据库或中间件性能调优时权衡不同方案成本的思维方式有异曲同工之妙，都是通过系统化搜索找到全局最优解。

解题思路：DFS + 记忆化搜索

直接暴力枚举所有购买组合会因分支过多而导致复杂度爆炸。题目给出的两个关键限制为高效搜索提供了可能：

1. 商品种类 n 很小（通常 ≤ 6）。
2. 每种商品的需求量也不大。

这提示我们可以采用「深度优先搜索(DFS)配合记忆化」的方法：

• 状态定义：将“当前剩余需求”作为一个状态，例如 (2, 1, 0) 表示还需购买商品0两个、商品1一个、商品2零个。
• 递归函数：定义 dfs(current_needs) 为满足当前剩余需求所需的最小花费。
• 基准方案：最直接的方式是放弃所有礼包，全部按单价购买：sum(current_needs[i] * price[i])。这为一个合法的保底解。
• 状态转移：尝试应用每一个有效的大礼包。对于礼包 offer：
  1. 检查是否可用：必须满足对于所有商品 i，都有 current_needs[i] >= offer[i]，否则会导致超买。
  2. 若可用，则计算新状态 next_needs[i] = current_needs[i] - offer[i]，并递归计算 offer_price + dfs(next_needs)。
• 取最小值：在所有可用的礼包方案与基准单价方案中，取花费最小的一个。
• 记忆化：使用缓存（如字典或 lru_cache）存储已计算过的状态结果，避免重复计算，这是将指数级搜索优化为可行解的关键。

Python代码实现

以下是利用 functools.lru_cache 实现记忆化搜索的典型代码：

from functools import lru_cache
from typing import List

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        n = len(price)
        # 预处理：过滤掉不比单买更划算的礼包
        valid_special = []
        for offer in special:
            offer_cnt = offer[:n]
            offer_price = offer[-1]
            # 计算礼包内商品按单价购买的总价
            origin_cost = sum(offer_cnt[i] * price[i] for i in range(n))
            # 仅保留有优惠的礼包
            if offer_price < origin_cost:
                valid_special.append(offer)

        @lru_cache(maxsize=None)
        def dfs(cur_needs: tuple) -> int:
            # 基准成本：全部单买
            min_cost = sum(cur_needs[i] * price[i] for i in range(n))

            # 尝试应用每一个有效礼包
            for offer in valid_special:
                offer_cnt = offer[:n]
                offer_price = offer[-1]

                # 检查当前礼包是否可用（是否会导致超买）
                next_needs = []
                usable = True
                for i in range(n):
                    if offer_cnt[i] > cur_needs[i]:
                        usable = False
                        break
                    next_needs.append(cur_needs[i] - offer_cnt[i])

                if not usable:
                    continue

                # 递归计算使用该礼包后的总成本
                total_with_offer = offer_price + dfs(tuple(next_needs))
                # 更新最小成本
                if total_with_offer < min_cost:
                    min_cost = total_with_offer

            return min_cost

        # 初始状态为需求列表转换成的元组（不可变，可作为缓存键）
        return dfs(tuple(needs))

代码要点说明：

1. 礼包预处理：提前剔除那些总价不低于内部商品单价之和的礼包，可以有效减少递归分支，提升效率。
2. 状态表示：递归函数的参数 cur_needs 必须是不可变类型（这里使用 tuple），才能被 lru_cache 正确缓存。
3. 记忆化装饰器：@lru_cache(maxsize=None) 自动处理结果的存储与复用，简化了代码。

复杂度分析

由于商品种类 n 和单种商品最大需求数量都很小，通过记忆化，实际需要计算的不同状态数量是有限的。每个状态在计算时会遍历所有礼包，因此整体时间复杂度与状态数及礼包数相关。对于该问题的数据范围，此方法是完全可行的。

总结

“大礼包”问题的核心在于将多维的剩余需求视为状态，通过DFS枚举所有可能的礼包使用组合，并利用记忆化避免子问题的重复计算，从而在可接受的时间内找到全局最优解。掌握这种“状态化”和“记忆化搜索”的思想，对于解决许多类似的组合优化问题至关重要。