Java optimal solution without memorization with explanation

• 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;
}
``````

• The running time is ~6^100

This sounds not very "optimal" :)

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