Java 8, recursion with cache, very short solution


  • 1

    The idea behind the recursion is :

    • at every stage, return the lowest of the two choices of including this special offer and excluding this special offer.
    • use a cache to store the intermediate results
    public static int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int index, Map<String, Integer> map) {
            int lowest = Integer.MAX_VALUE;
            if(needs.stream().allMatch(x -> x == 0)) return 0;
            String key = needs.stream().map(x -> ""+x).collect(Collectors.joining(" "));
            if(map.containsKey(key)) return map.get(key);
    
            if(index == special.size()) {
                return IntStream.range(0, needs.size()).map(i -> needs.get(i) * price.get(i)).sum();
            }
            List<Integer> updatedNeeds = IntStream.range(0, needs.size()).mapToObj(i -> needs.get(i) - special.get(index).get(i)).collect(Collectors.toList());
            if(updatedNeeds.stream().allMatch(x -> x >= 0) ){
                lowest = Math.min(lowest, special.get(index).get(special.get(index).size() - 1) + shoppingOffers(price, special, updatedNeeds, index, map));
            }
            return Math.min(lowest, shoppingOffers(price, special, needs, index + 1, map));
        }
    

Log in to reply
 

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