友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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 个大礼包的价格。
返回 确切 满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。
示例 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 -
生成的输入对于
0 <= j <= n - 1至少有一个special[i][j]非零。
思路分析
没想到是动态规划。
-
一刷(暴力破解)
-
一刷(备忘录)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
* 暴力破解（11.29%）
*
* @author D瓜哥 · https://www.diguage.com
* @since 2026-04-14 21:47:37
*/
public int shoppingOffers(List<Integer> price,
List<List<Integer>> special,
List<Integer> needs) {
int size = price.size();
List<List<Integer>> filtered = special.stream()
.filter(s -> {
int count = 0, sum = 0;
for (int i = 0; i < size; i++) {
count += s.get(i);
sum += s.get(i) * price.get(i);
}
return count > 0 && sum > s.getLast();
}).toList();
// 暴力破解
return dfs(price, filtered, needs);
}
private int dfs(List<Integer> price, List<List<Integer>> specials, List<Integer> needs) {
int result = 0;
for (int i = 0; i < needs.size(); i++) {
result += price.get(i) * needs.get(i);
}
int n = price.size();
for (List<Integer> spec : specials) {
List<Integer> nextNeeds = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (spec.get(i) > needs.get(i)) {
break;
}
nextNeeds.add(needs.get(i) - spec.get(i));
}
if (nextNeeds.size() == n) {
result = Math.min(result, dfs(price, specials, nextNeeds) + spec.get(n));
}
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* 暴力破解（11.29%） -> 备忘录（25.81%）
*
* @author D瓜哥 · https://www.diguage.com
* @since 2026-04-14 22:07:03
*/
public int shoppingOffers(List<Integer> price,
List<List<Integer>> special,
List<Integer> needs) {
int size = price.size();
List<List<Integer>> filtered = special.stream()
.filter(s -> {
int count = 0, sum = 0;
for (int i = 0; i < size; i++) {
count += s.get(i);
sum += s.get(i) * price.get(i);
}
return count > 0 && sum > s.getLast();
}).toList();
Map<List<Integer>, Integer> memo = new HashMap<>();
return dfs(price, filtered, needs, memo);
}
private int dfs(List<Integer> price, List<List<Integer>> specials,
List<Integer> needs, Map<List<Integer>, Integer> memo) {
if (memo.containsKey(needs)) {
return memo.get(needs);
}
int result = 0;
for (int i = 0; i < needs.size(); i++) {
result += price.get(i) * needs.get(i);
}
int n = price.size();
for (List<Integer> spec : specials) {
List<Integer> nextNeeds = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (spec.get(i) > needs.get(i)) {
break;
}
nextNeeds.add(needs.get(i) - spec.get(i));
}
if (nextNeeds.size() == n) {
result = Math.min(result, dfs(price, specials, nextNeeds, memo) + spec.get(n));
}
}
memo.put(needs, result);
return result;
}