# 0638. Shopping Offers
###### tags: `Leetcode` `Medium` `DFS+Memorization`
Link: https://leetcode.com/problems/shopping-offers/
## 思路
memorization里面需要记录每一组needs的cost的最小值
如果直接用list of integer当map的key比较麻烦
所以把整个list用```needs.toString()```转成string
但如果直接这样写
[4,9,6]
[[0,1,1,5],[2,3,2,1],[1,2,1,7],[1,0,0,2]]
[4,5,3]
Output : 19 Expected: 10
这个testcase会有问题
因为expected应该用后三个 但是[2,2,1]这个need (本来最佳解应该是由```needs-special[1]```得到) 但它会先从```needs-special[0]-special[2]-2*special[3]```得到
所以为了区分在key里面还加了start
## Code

class Solution {
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        Map<String, Integer> minCost = new HashMap<>();
        return dfs(price, special, needs, minCost, 0);
    }
    private int dfs(List<Integer> price, List<List<Integer>> special, List<Integer> needs, Map<String, Integer> minCost, int start){
        if(minCost.containsKey(needs.toString()+start)) return minCost.get(needs.toString()+start);
        int min = directPurchase(price, needs);
        for(int i=start; i<special.size(); i++){
            List<Integer> nextNeeds = new ArrayList<>();
            for(int j=0; j<needs.size(); j++){
                if(needs.get(j) < special.get(i).get(j)) break;
                nextNeeds.add(needs.get(j)-special.get(i).get(j));
            }
            if(nextNeeds.size()==needs.size()){
                min = Math.min(min, dfs(price, special, nextNeeds, minCost, i)+special.get(i).get(special.get(i).size()-1));
            }
        }
        minCost.put(needs.toString()+start, min);
        return min;
    }
    private int directPurchase(List<Integer> price, List<Integer> needs){
        int cost = 0;
        for(int i=0; i<needs.size(); i++){
            cost += price.get(i)*needs.get(i);
        }
        return cost;
    }
}