# Intuitive DFS with memorization Java solution

• Solution based on the algorithm.

``````static int shoppingOffersII(List<Integer> price, List<List<Integer>> sp, List<Integer> needs) {
Map<List<Integer>, Integer> map = new HashMap<>();
return shoppingII(price, sp, needs, map);
}
static int shoppingII(List<Integer> price, List<List<Integer>> sp, List<Integer> needs, Map<List<Integer>, Integer> map) {
if (map.containsKey(needs))	return map.get(needs);
boolean flag = true;
for (int cnt : needs) {
if (cnt != 0) flag = false;
}
if (flag)	return 0;
int normal = 0;
for (int i = 0;  i < needs.size(); i++) {
normal += price.get(i) * needs.get(i);
}
for (List<Integer> offer: sp) {
//  judge whether all elements in <code>needs</code> is 0
int pay = 0;
int i = 0;
for (; i < offer.size()-1; i++) {
if (offer.get(i) > needs.get(i))
break;
}
if (i >= offer.size()-1) { // each items' count in this offer <=  needs' corresponding count
List<Integer> clone = new ArrayList<>(needs);
for (int j = 0; j < clone.size(); j++) {
int updated = needs.get(j) - offer.get(j);
clone.set(j, updated);
}
pay = shoppingII(price, sp, clone, map);
pay += offer.get(offer.size()-1);	// add offer itself price
if (pay < normal)	normal = pay;
}
}
map.put(needs, normal);	// use memorization
return normal;
}``````

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