https://leetcode.com/problems/shopping-offers/description/
解题思路：
- 首先确定其停止（返回）条件
- 确定其深度搜索范围
- 返回当前值
class Solution {
Map<List<Integer>, Integer> map = new HashMap<>();
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
if(map.containsKey(needs)) return map.get(needs);
int sum = Integer.MAX_VALUE;
for(List<Integer> offer : special){
List<Integer> reducedNeeds = new ArrayList<>();
boolean validSpecial = true;
for(int i = 0; i < needs.size(); i++){
reducedNeeds.add( needs.get(i) - offer.get(i));
if(reducedNeeds.get(i) < 0){
validSpecial = false;
break;
}
}
if(validSpecial){
sum = Math.min(sum, offer.get(offer.size() - 1) + shoppingOffers(price, special, reducedNeeds));
}
}
int normal = 0;
for(int i = 0; i < needs.size(); i++){
normal += price.get(i) * needs.get(i);
}
sum = Math.min(sum, normal);
map.put(needs, sum);
return sum;
}
}
