Easy to understand Java recursive solution 15ms


  • 0
    X
    public class Solution {
        
        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            return findLower(price, special, needs, 0);
        }
        
        int findLower(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int index) {        
            int newPrice = noCouponPrice(price, needs);
            for (int i = index; i < special.size(); i++) {
                List<Integer> newNeeds = new ArrayList();
                for (int j = 0; j < needs.size(); j++) {
                    if (needs.get(j) - special.get(i).get(j) >= 0)
                        newNeeds.add(needs.get(j) - special.get(i).get(j));
                    else
                        break;
                }
                
                if (newNeeds.size() == needs.size()) {
                    newPrice = Math.min(newPrice, special.get(i).get(needs.size()) + findLower(price, special, newNeeds, i));                
                }   
            }
            return newPrice;
        }
        
        int noCouponPrice(List<Integer> price, List<Integer> needs) {
            int newPrice = 0;
            for (int i = 0; i < needs.size(); i++) {
                newPrice += needs.get(i) * price.get(i);
            }
            
            return newPrice;
        }
    }
    

Log in to reply
 

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