Problem

In LeetCode Store, there are some kinds of items to sell. Each item has a price.

However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given the each item's price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.

Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.

You could use any of special offers as many times as you want.

Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]

Output: 14

Explanation: 
There are two kinds of items, A and B. Their prices are $2 and $5 respectively. 
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B. 
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]

Output: 11

Explanation: 
The price of A is $2, and $3 for B, $4 for C. 
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. 
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. 
You cannot add more items, though only $9 for 2A ,2B and 1C.

Note:

1. There are at most 6 kinds of items, 100 special offers.
2. For each item, you need to buy at most 6 of them.
3. You are not allowed to buy more items than you want, even if that would lower the overall price.

思路

• 求满足需求的最小cost
• 因为special offer和需求并没有顺序， 因此想到用暴力dfs来遍历所有的解决方案，从而得出最小的cost
• 这个dfs怎么定义？
  • 先解决一小嘬需求，然后通过递归得到剩下需求的最小cost，合并到最终。
  • solution的每层都是一个offer， 因为不确定用那个，用多少个，所以需要用dfs。
  • 而且每一层都要计算不需要special offer的cost，作比较，取最小者
  • 这样子递归下来，一个solution就是special offer和普通offer的组合

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < special.size(); i++) {
            List<Integer> offer = special.get(i);
            List<Integer> subNeeds = new ArrayList<>();
            boolean validOffer = true;
            for (int j = 0; j < needs.size(); j++) {
                subNeeds.add(needs.get(j) - offer.get(j));
                if (subNeeds.get(j) < 0) {
                    validOffer = false;
                    break;
                }
            }
            if (!validOffer) continue;
            result = Math.min(result, offer.get(offer.size() - 1) + shoppingOffers(price, special, subNeeds));
        }

        int nonSpecial = 0;
        for (int i = 0; i < price.size(); i++) {
            nonSpecial += price.get(i) * needs.get(i);
        }
        return Math.min(result, nonSpecial);
    }

优化（保存已求得mincost的需求）

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        return shoppingOffers(price, special, needs, new HashMap<List<Integer>, Integer>());
    }

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs, Map<List<Integer>, Integer> dp) {
        if (dp.containsKey(needs)) return dp.get(needs);
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < special.size(); i++) {
            List<Integer> offer = special.get(i);
            List<Integer> subNeeds = new ArrayList<>();
            boolean validOffer = true;
            for (int j = 0; j < needs.size(); j++) {
                subNeeds.add(needs.get(j) - offer.get(j));
                if (subNeeds.get(j) < 0) {
                    validOffer = false;
                    break;
                }
            }
            if (!validOffer) continue;
            result = Math.min(result, offer.get(offer.size() - 1) + shoppingOffers(price, special, subNeeds, dp));
        }

        int nonSpecial = 0;
        for (int i = 0; i < price.size(); i++) {
            nonSpecial += price.get(i) * needs.get(i);
        }
        result = Math.min(result, nonSpecial);
        dp.put(needs, result);