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 = [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 。

输入：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 更加便宜。

题解：

方法：记忆化搜索
思路：借鉴了【微扰理论】大佬的思路，在暴力递归的基础上，加入cache哈希表作为缓存，之后进行暴力递归，如果发现当前的needs在cache中，就直接返回，如果不在，就进行暴力递归，并且找到最小的花费，最后将这次的needs加入到cache缓存中，方便下次搜索。

代码：

//相当于记忆化搜索的dp，就是缓存，用于记录每次找过的需求
Map<List<Integer>, Integer> cache = new HashMap<>();
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
    return dfs(needs, price, special);
}

public int dfs(List<Integer> needs, List<Integer> price, List<List<Integer>> special) {
    //如果以前计算过这个needs，就直接返回
    if (cache.containsKey(needs))
        return cache.get(needs);
    int ans = 0;
    //最简单的方法，不买礼包，
    for (int i = 0; i < needs.size(); i++) {
        ans += needs.get(i) * price.get(i);
    }
    //遍历和购买每个礼包，找到最便宜的价格
    for (int i = 0; i < special.size(); i++) {
        List<Integer> next = new ArrayList<>(needs);
        boolean flag = true;
        for (int item = 0; item < price.size(); item++) {
            //购买数量不能超过needs，所以，如果礼包里面物品的数量大于了needs里面对应物品的数量就不买这个大礼包
            if (special.get(i).get(item) > needs.get(item)) {
                flag = false;
                break;
            }
        }
        //大礼包不符合要求，跳过这个大礼包，不购买
        if (!flag) continue;
        //当前大礼包符合要求，用next数组记录购买这个大礼包后，还需要各种物品的数量，并带入next基于递归
        for (int item = 0; item < price.size(); item++) {
            next.set(item, next.get(item) - special.get(i).get(item));
        }
        //在所有的购买方法中找到最便宜的方法
        ans = Math.min(ans, dfs(next, price, special) + special.get(i).get(price.size()));
    }
    //递归结束后，更新我们的cache缓存，便于后面再次查找
    cache.put(needs, ans);
    return ans;
}