DFS with DP memory


  • 0
    L

    '''
    public class Solution {
    Map<List<Integer>, Integer> cost = new HashMap<>();
    List<List<Integer>> specials;
    List<Integer> price;

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
    	this.price = price;
    	this.specials = special;
    	return helper(0, needs);
    }
    
    private int helper(int specialPos, List<Integer> needs) {
    	if (cost.containsKey(needs)) {
    		return cost.get(needs);
    	}
    	int minCost = 0;
    	for (int i = 0; i < needs.size(); i++) {
    		minCost += needs.get(i) * price.get(i);
    	}
    	for (int i = specialPos; i < specials.size(); i++) {
    		List<Integer> special = specials.get(i);
    		List<Integer> subNeeds = new ArrayList<>(needs);
    		boolean canSpecial = true;
    		for (int j = 0; j < needs.size(); j++) {
    			subNeeds.set(j, subNeeds.get(j) - special.get(j));
    			if (subNeeds.get(j) < 0) {
    				canSpecial = false;
    			}
    		}
    		if (canSpecial) {
    			minCost = Math.min(minCost, special.get(special.size() - 1) + helper(i, subNeeds));
    		}
    	}
    	cost.put(needs, minCost);
    	return minCost;
    }
    

    }
    '''


Log in to reply
 

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