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
• n == needs.length
• 1 <= n <= 6
• 0 <= price[i] <= 10
• 0 <= needs[i] <= 10
• 1 <= special.length <= 100
• special[i].length == n + 1
• 0 <= special[i][j] <= 50

解題思路

1. 預處理special數組，如果大禮包內所有的物品數量都為0或者大禮包的單價小于所有物品的總價，則將其剔除出去。
2. 使用深度優先搜索，每一次遞歸就是選擇任意一份大禮包，或者不購買大禮包，全部按所需物品的單價購買，計算購買該大禮包以后，仍每種物品仍然需要的數量大小，進行下一次遞歸，如果超出購物清單指定數量的物品，則不進行遞歸，返回最小花費的組合方式。
3. 使用記憶化搜索，使用map記錄下，所需物品清單和其花費最低價格的映射，避免重復計算某種所需物品清單的最低價格。

代碼

class Solution {Map<List<Integer>, Integer> map = new HashMap<>();public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {List<List<Integer>> filter = new ArrayList<>();for (List<Integer> integerList : special) {int sum = 0, c = 0;for (int i = 0; i < integerList.size() - 1; i++) {sum += price.get(i) * integerList.get(i);c += integerList.get(i);}if (integerList.get(integerList.size() - 1) < sum && c > 0)filter.add(integerList);}return dfs(price, needs, filter);}public int dfs(List<Integer> price, List<Integer> needs, List<List<Integer>> special) {if (map.containsKey(needs)) {return map.get(needs);}int p = 0, n =  needs.size();for (int i = 0; i < needs.size(); i++) {p += needs.get(i) * price.get(i);}for (List<Integer> spec : special) {ArrayList<Integer> next = new ArrayList<>();for (int i = 0; i < n; i++) {if (spec.get(i) > needs.get(i)) {break;}next.add(needs.get(i) - spec.get(i));}if (next.size() == n)p = Math.min(p, spec.get(n) + dfs(price, next, special));}map.put(needs, p);return p;}}