Leetcode刷题Python之638.大礼包

提示：这道题是典型的“选择问题”。

---

一、题目描述

在 LeetCode 商店中， 有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i] 是需要购买第 i 件物品的数量。

还有一个数组 special 表示大礼包，special[i] 的长度为 n + 1 ，其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。

返回确切满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。

我们的目标是在满足购物清单的前提下，通过购买商品或使用大礼包来实现最低花费。

题目内容

price：一个长度为 n 的整数数组，表示每件商品的单价。
special：一个二维数组，每个子数组代表一个大礼包，前 n 个数字表示礼包中包含的各商品数量，最后一个数字为礼包总价。
needs：一个长度为 n 的数组，表示每件商品的需求数量。

示例：

示例1 ：输入：price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
输出：14
解释：有 A 和 B 两种商品，单价分别为 ¥2 和 ¥5 。大礼包 1，可以以 ¥5 购买 3A 和 0B。大礼包 2，可以以 ¥10 购买 1A 和 2B。为了满足需求 3A 和 2B，可用大礼包 2（花费 ¥10），再单独购买 2A（花费 ¥4），总共花费 ¥14。

二、题目解析

1.需求限制：购买的大礼包内物品数量不能超过需求，也就是说不能超量购买商品。

2.无限次购买礼包：只要满足需求，礼包可以多次购买，但每次购买会消耗一定成本。

3.求最小总花费：我们既可以选择单独购买商品，也可以组合使用大礼包，求最小的满足需求的总花费。

思路分析

这个问题可以分解成每一步选择用或者不用大礼包的组合问题。我们可以使用递归的深度优先搜索（DFS）来尝试每种情况，并使用记忆化技术来优化重复计算。

1.基本方法：

不使用大礼包时的总花费 = 每件商品需求数量 * 单价的总和。
尝试使用大礼包，在需求量范围内应用礼包来减少商品的需求量，并将剩余需求递归计算出花费。

2.递归策略：

对于每种需求状态，计算出使用某个礼包后的新需求状态。
对比使用和不使用礼包的成本，取最小值作为当前需求状态的最小花费。

3.记忆化：

为了避免重复计算，用一个字典 memo 来存储不同需求状态对应的最小花费。
当某个需求组合已经计算过时，直接取缓存结果。

---

三、代码实现

class Solution(object):def shoppingOffers(self, price, special, needs):""":type price: List[int]:type special: List[List[int]]:type needs: List[int]:rtype: int"""# 记忆化字典，用于存储每种需求状态下的最低花费memo = {}def dfs(current_needs):# 转换为元组，以便哈希存储needs_tuple = tuple(current_needs)# 如果当前需求状态已经在 memo 中，直接返回存储的最小花费if needs_tuple in memo:return memo[needs_tuple]# 不使用任何大礼包时的最低花费，即逐件单独购买的总花费min_cost = sum(need * price[i] for i, need in enumerate(current_needs))# 遍历每个大礼包，尝试用礼包来满足当前需求for offer in special:# 用来存储新需求状态new_needs = []for i in range(len(current_needs)):# 如果某个商品在当前需求中少于礼包中的数量，无法使用该礼包if current_needs[i] < offer[i]:break# 减去礼包内商品数量，计算新的需求状态new_needs.append(current_needs[i] - offer[i])else:# 如果所有需求都满足礼包条件，递归计算剩余需求的最低花费min_cost = min(min_cost, dfs(new_needs) + offer[-1])# 存储当前需求状态下的最小花费，以便记忆化优化memo[needs_tuple] = min_costreturn min_cost# 从初始需求开始计算最低花费return dfs(needs)

---

详细解释

dfs函数：此函数用于深度优先搜索（DFS），在当前需求状态下递归尝试各种大礼包组合。

记忆化：memo字典缓存已经计算过的需求组合，以减少重复计算。

不使用礼包的情况：当不使用礼包时，直接按单价购买所需商品数量，计算的花费就是“每件商品需求数量 * 单价”的和。

礼包有效性检查：对每个礼包，逐一检查是否满足当前需求；如果任何一件商品的需求低于礼包内数量，跳过该礼包。

四、总结

时间复杂度和空间复杂度分析

时间复杂度：由于记忆化减少了重复计算，每种需求状态的复杂度取决于礼包数量和需求组合数。总体时间复杂度较难精确估计，但在给定数据约束下，表现稳定。

空间复杂度：主要是memo字典的空间开销，用于存储已计算过的需求状态。

评价

这道题是典型的“选择问题”：我们要在多种可能的选择中找到最优解。递归和记忆化的结合非常适合这种逐层拆分的组合问题。通过将每一种需求状态存储在记忆化字典中，我们显著提高了递归的效率。