Medium

题目描述

在 LeetCode 商店中，有 n 种物品出售。每种物品都有一个价格。然而，也有一些大礼包优惠，每个大礼包以优惠的价格捆绑销售一定数量的物品中的几种。

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

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

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

示例 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 。
需要购买 3 个 A 和 2 个 B ， 所以付 ¥10 购买 1A 和 2B（大礼包 2），以及 ¥4 购买 2A 。

示例 2：

输入：price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]
输出：11
解释：A ，B ，C 的价格分别为 ¥2 ，¥3 ，¥4 。
可以用 ¥4 购买 1A 和 1B ，也可以用 ¥9 购买 2A ，2B 和 1C 。
需要买 1A ，2B 和 1C ，所以付 ¥4 买 1A 和 1B（大礼包 1），以及 ¥3 购买 1B ， ¥4 购买 1C 。
不可以购买超出待购清单的物品，尽管购买大礼包 2 更加便宜。

提示：

  • n == price.length == needs.length
  • 1 <= n <= 6
  • 0 <= price[i], needs[i] <= 10
  • 1 <= special.length <= 100
  • special[i].length == n + 1
  • 0 <= special[i][j] <= 50

解题思路

这是一个典型的递归搜索 + 记忆化优化问题，主要思路如下：

核心思想： 对于当前的购物需求，我们有两种选择策略：

  1. 直接按单价购买剩余的物品
  2. 使用某个大礼包（如果适用），然后递归处理剩余需求

算法步骤：

  1. 首先计算直接购买所有物品的基础成本作为初始答案
  2. 遍历所有大礼包，检查是否可以使用（即礼包中的物品数量不超过当前需求）
  3. 如果可以使用某个礼包，计算使用后的新需求，递归求解剩余问题
  4. 比较所有可能方案，选择最小成本

优化技巧：

  • 使用记忆化搜索避免重复计算相同状态
  • 预先过滤掉不划算的大礼包（价格不低于单独购买）
  • 由于 n ≤ 6 且每个需求 ≤ 10，状态空间较小，记忆化效果显著

时间复杂度： 状态数量为 O(11^n)，每个状态需要遍历所有礼包，总体复杂度可接受。

代码实现

class Solution {
public:
    unordered_map<string, int> memo;
    
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        // 过滤掉不划算的大礼包
        vector<vector<int>> validSpecial;
        for (auto& spec : special) {
            int directCost = 0;
            for (int i = 0; i < price.size(); i++) {
                directCost += spec[i] * price[i];
            }
            if (spec.back() < directCost) {
                validSpecial.push_back(spec);
            }
        }
        return dfs(price, validSpecial, needs);
    }
    
private:
    int dfs(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        string key = "";
        for (int need : needs) {
            key += to_string(need) + ",";
        }
        if (memo.count(key)) {
            return memo[key];
        }
        
        // 直接购买的成本
        int directCost = 0;
        for (int i = 0; i < price.size(); i++) {
            directCost += needs[i] * price[i];
        }
        
        int minCost = directCost;
        
        // 尝试每个大礼包
        for (auto& spec : special) {
            vector<int> newNeeds = needs;
            bool canUse = true;
            
            // 检查是否可以使用这个礼包
            for (int i = 0; i < price.size(); i++) {
                if (newNeeds[i] < spec[i]) {
                    canUse = false;
                    break;
                }
                newNeeds[i] -= spec[i];
            }
            
            if (canUse) {
                minCost = min(minCost, spec.back() + dfs(price, special, newNeeds));
            }
        }
        
        return memo[key] = minCost;
    }
};

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        # 过滤掉不划算的大礼包
        valid_special = []
        for spec in special:
            direct_cost = sum(spec[i] * price[i] for i in range(len(price)))
            if spec[-1] < direct_cost:
                valid_special.append(spec)
        
        memo = {}
        
        def dfs(needs):
            key = tuple(needs)
            if key in memo:
                return memo[key]
            
            # 直接购买的成本
            direct_cost = sum(needs[i] * price[i] for i in range(len(price)))
            min_cost = direct_cost
            
            # 尝试每个大礼包
            for spec in valid_special:
                new_needs = []
                can_use = True
                
                # 检查是否可以使用这个礼包
                for i in range(len(price)):
                    if needs[i] < spec[i]:
                        can_use = False
                        break
                    new_needs.append(needs[i] - spec[i])
                
                if can_use:
                    min_cost = min(min_cost, spec[-1] + dfs(new_needs))
            
            memo[key] = min_cost
            return min_cost
        
        return dfs(needs)

public class Solution {
    private Dictionary<string, int> memo = new Dictionary<string, int>();
    
    public int ShoppingOffers(IList<int> price, IList<IList<int>> special, IList<int> needs) {
        // 过滤掉不划算的大礼包
        var validSpecial = new List<IList<int>>();
        foreach (var spec in special) {
            int directCost = 0;
            for (int i = 0; i < price.Count; i++) {
                directCost += spec[i] * price[i];
            }
            if (spec[spec.Count - 1] < directCost) {
                validSpecial.Add(spec);
            }
        }
        
        return Dfs(price, validSpecial, needs.ToArray());
    }
    
    private int Dfs(IList<int> price, List<IList<int>> special, int[] needs) {
        string key = string.Join(",", needs);
        if (memo.ContainsKey(key)) {
            return memo[key];
        }
        
        // 直接购买的成本
        int directCost = 0;
        for (int i = 0; i < price.Count; i++) {
            directCost += needs[i] * price[i];
        }
        
        int minCost = directCost;
        
        // 尝试每个大礼包
        foreach (var spec in special) {
            var newNeeds = new int[needs.Length];
            bool canUse = true;
            
            // 检查是否可以使用这个礼包
            for (int i = 0; i < price.Count; i++) {
                if (needs[i] < spec[i]) {
                    canUse = false;
                    break;
                }
                newNeeds[i] = needs[i] - spec[i];
            }
            
            if (canUse) {
                minCost = Math.Min(minCost, spec[spec.Count - 1] + Dfs(price, special, newNeeds));
            }
        }
        
        return memo[key] = minCost;
    }
}

var shoppingOffers = function(price, special, needs) {
    // 过滤掉不划算的大礼包
    const validSpecial = [];
    for (const spec of special) {
        let directCost = 0;
        for (let i = 0; i < price.length; i++) {
            directCost += spec[i] * price[i];
        }
        if (spec[spec.length - 1] < directCost) {
            validSpecial.push(spec);
        }
    }
    
    const memo = new Map();
    
    function dfs(needs) {
        const key = needs.join(',');
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        // 直接购买的成本
        let directCost = 0;
        for (let i = 0; i < price.length; i++) {
            directCost += needs[i] * price[i];
        }
        
        let minCost = directCost;
        
        // 尝试每个大礼包
        for (const spec of validSpecial) {
            const newNeeds = [];
            let canUse = true;
            
            // 检查是否可以使用这个礼包
            for (let i = 0; i < price.length; i++) {
                if (needs[i] < spec[i]) {
                    canUse = false;
                    break;
                }
                newNeeds.push(needs[i] - spec[i]);
            }
            
            if (canUse) {
                minCost = Math.min(minCost, spec[spec.length - 1] + dfs(newNeeds));
            }
        }
        
        memo.set(key, minCost);
        return minCost;
    }
    
    return dfs(needs);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(S × 11^n)，其中 S 是有效大礼包数量，n 是物品种类，11^n 是可能的状态数量
空间复杂度O(11^n)，用于记忆化存储和递归调用栈