美文网首页
638. Shopping Offers

638. Shopping Offers

作者: becauseyou_90cd | 来源:发表于2018-07-22 01:25 被阅读0次

https://leetcode.com/problems/shopping-offers/description/

解题思路:

  1. 首先确定其停止(返回)条件
  2. 确定其深度搜索范围
  3. 返回当前值

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

}

相关文章

网友评论

      本文标题:638. Shopping Offers

      本文链接:https://www.haomeiwen.com/subject/psnkmftx.html