Java 26ms recursive solution (no DP)


  • 0
    K

    Use index to mark how many offers we have seen. In the next call, visit the current offer or any offer after the current offer.

        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            return helper(price, special, needs, 0);
        }
        private int helper(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int index) {
            int min = 0;
            for (int j = 0; j < needs.size(); j++) {
                min += needs.get(j) * price.get(j);
            }
            
            for (int i = index; i < special.size(); i++) {
                List<Integer> offer = special.get(i);
                List<Integer> copy = new ArrayList<>(needs);
                boolean validOffer = true;
                for (int j = 0; j < copy.size(); j++) {
                    copy.set(j, copy.get(j) - offer.get(j));
                    if (copy.get(j) < 0) {
                        validOffer = false;
                        break;
                    }
                }
                if (validOffer) 
                    min = Math.min(min, helper(price, special, copy, index) + offer.get(offer.size() - 1));
            }
            return min;
        }
    

Log in to reply
 

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