Intuitive DFS with memorization Java solution


  • 0
    S

    Solution based on the algorithm.

    static int shoppingOffersII(List<Integer> price, List<List<Integer>> sp, List<Integer> needs) {
    		Map<List<Integer>, Integer> map = new HashMap<>();
    		return shoppingII(price, sp, needs, map);
    	}
    	static int shoppingII(List<Integer> price, List<List<Integer>> sp, List<Integer> needs, Map<List<Integer>, Integer> map) {
    		if (map.containsKey(needs))	return map.get(needs);
    		boolean flag = true;
    		for (int cnt : needs) {
    			if (cnt != 0) flag = false;
    		}
    		if (flag)	return 0;
    		int normal = 0;
    		for (int i = 0;  i < needs.size(); i++) {
    			normal += price.get(i) * needs.get(i);
    		}
    		for (List<Integer> offer: sp) {
    			//  judge whether all elements in <code>needs</code> is 0
    			int pay = 0;
    			int i = 0;
    			for (; i < offer.size()-1; i++) {
    				if (offer.get(i) > needs.get(i))
    					break;
    			}
    			if (i >= offer.size()-1) { // each items' count in this offer <=  needs' corresponding count
    				List<Integer> clone = new ArrayList<>(needs);
    				for (int j = 0; j < clone.size(); j++) {
    					int updated = needs.get(j) - offer.get(j);
    					clone.set(j, updated);
    				}
    				pay = shoppingII(price, sp, clone, map);
    				pay += offer.get(offer.size()-1);	// add offer itself price
    				if (pay < normal)	normal = pay;
    			}	
    		}
    		map.put(needs, normal);	// use memorization
    		return normal;
            }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.