Simple Java Solution, use HashMap


  • 0
    J
    class Solution {
        Map<String, Integer> map;
        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            if(needs == null || needs.size() == 0)
                return 0;
            int n = needs.size();
            map = new HashMap<>();
            return minPrice(price, special, needs); 
        }
        
        private int minPrice(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            int min = Integer.MAX_VALUE;
            String key = needs.toString();
            if(!map.containsKey(key)) {
                int sum = 0;
                for(int need: needs)
                    sum += need;
                if(sum == 0) {
                    map.put(key, 0);
                    return 0;
                }
                for(List<Integer> list : special) {
                    boolean isllegal = true;
                    List<Integer> tmp = new ArrayList<>();
                    for(int i =0; i < list.size() - 1; i++) {
                        if(needs.get(i) < list.get(i)) {
                            isllegal = false;
                            break;
                        }
                        tmp.add(needs.get(i) - list.get(i));
                    }
                    if(isllegal) {
                        min = Math.min(min, list.get(list.size() - 1) + minPrice(price, special, tmp));
                    }
                }
                int noPrices = 0;
                for(int i = 0; i < needs.size(); i++) {
                    noPrices += price.get(i) * needs.get(i);
                }
                min = Math.min(min, noPrices);
                map.put(key, min);
            }
            return map.get(key);
        }
    }
    

Log in to reply
 

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