Java optimal solution without memorization with explanation


  • 1
    P

    Let's take a look at the structure of the data:
    There are at most 6 kinds of items, 100 special offers.
    For each item, you need to buy at most 6 of them.

    We can see that:

    • applying offers decrease amount at least by one
    • max usage number of the same offer is 6

    It would be easier to think about this problem as of a tree.
    Every offer is a node, and it can have at most 6 edges (numbers of times an offer was used). The tree depth is 100.

    The running time is ~6^100 and space complexity is ~100 (depth of recursion/tree)
    The memorization is not needed because all combinations (paths) with promotions are unique.

        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            int[] needsArray = new int[needs.size()];
            for(int i = 0; i < needsArray.length;i++) {
                needsArray[i] = needs.get(i);
            }
    
            return minAmount(price, special, needsArray) ;
        }
    
        int minAmount(List<Integer> price, List<List<Integer>> specials, int[] needs) {
    
            int amountToPay = 0;
    
            if (specials.isEmpty()) {
                // There are no special offers, so just buying the needed amount
                for (int i = 0; i < needs.length; i++) {
                    amountToPay += needs[i] * price.get(i);
                }
    
                return amountToPay;
            }
    
            List<Integer> special = specials.remove(specials.size() - 1);
            int minAmount = Integer.MAX_VALUE;
    
            boolean canApplyOffer = true;
            int count = 0;
            final int offerPriceIndex = needs.length;
    
            while (canApplyOffer) {
    
                amountToPay = minAmount(price, specials, needs);
                minAmount = Math.min(minAmount, special.get(offerPriceIndex) * count + amountToPay);
    
                for (int j = 0; j < needs.length; j++) {
                    needs[j] -= special.get(j);
    
                    if (needs[j] < 0) {
                        canApplyOffer = false;
                    }
                }
    
                count++;
            }
    
            // Restore "needs" array
            for (int i = 0; i < needs.length; i++) {
                needs[i] += special.get(i) * count;
            }
    
            // Restore offers list
            specials.add(special);
    
            return minAmount;
        }
    

  • 0
    T

    @prrr:

    The running time is ~6^100

    This sounds not very "optimal" :)


Log in to reply
 

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