add 638

fishercoder1534 · fishercoder1534 · commit 3fad8b182843 · 2017-07-11T21:56:59.000-07:00
diff --git a/README.md b/README.md
@@ -21,6 +21,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |  #  |      Title     |   Solutions   | Time          | Space         | Difficulty  | Tag          | Notes
 |-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
 |640|[Solve the Equation](https://leetcode.com/problems/solve-the-equation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_640.java) | O(n) |O(n) | Medium |
+|638|[Shopping Offers](https://leetcode.com/problems/shopping-offers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_638.java) | O(2^n) |O(n) | Medium | DP, DFS
 |637|[Average of Levels in Binary Tree](https://leetcode.com/problems/average-of-levels-in-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_637.java) | O(n) |O(1) | Easy | 
 |634|[Find the Derangement of An Array](https://leetcode.com/problems/find-the-derangement-of-an-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_634.java) | O(n) |O(1) | Medium | Math
 |633|[Sum of Square Numbers](https://leetcode.com/problems/sum-of-square-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_633.java) | O(logn) |O(1) | Easy | Binary Search
diff --git a/src/main/java/com/fishercoder/solutions/_638.java b/src/main/java/com/fishercoder/solutions/_638.java
@@ -0,0 +1,74 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * 638. Shopping Offers
+ *
+ * In LeetCode Store, there are some kinds of items to sell. Each item has a price.
+ * However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
+ * You are given the each item's price, a set of special offers,
+ * and the number we need to buy for each item.
+ * The job is to output the lowest price you have to pay for exactly certain items as given,
+ * where you could make optimal use of the special offers.
+ * Each special offer is represented in the form of an array,
+ * the last number represents the price you need to pay for this special offer,
+ * other numbers represents how many specific items you could get if you buy this offer.
+ * You could use any of special offers as many times as you want.
+
+ Example 1:
+ Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
+ Output: 14
+ Explanation:
+ There are two kinds of items, A and B. Their prices are $2 and $5 respectively.
+ In special offer 1, you can pay $5 for 3A and 0B
+ In special offer 2, you can pay $10 for 1A and 2B.
+ You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.
+
+ Example 2:
+ Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
+ Output: 11
+ Explanation:
+ The price of A is $2, and $3 for B, $4 for C.
+ You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
+ You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C.
+ You cannot add more items, though only $9 for 2A ,2B and 1C.
+
+ Note:
+ There are at most 6 kinds of items, 100 special offers.
+ For each item, you need to buy at most 6 of them.
+ You are not allowed to buy more items than you want, even if that would lower the overall price.
+ */
+public class _638 {
+    /**reference: https://leetcode.com/articles/shopping-offers/#approach-1-using-recursion-accepted*/
+    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
+        return shopping(price, special, needs, 0);
+    }
+
+    public int shopping(List < Integer > price, List < List < Integer >> special, List < Integer > needs, int i) {
+        if (i == special.size()) {
+            return dot(needs, price);
+        }
+        ArrayList<Integer> clone = new ArrayList(needs);
+        int j = 0;
+        for (j = 0; j < special.get(i).size() - 1; j++) {
+            int diff = clone.get(j) - special.get(i).get(j);
+            if (diff < 0) break;
+            clone.set(j, diff);
+        }
+        if (j == special.get(i).size() - 1) {
+            return Math.min(special.get(i).get(j) + shopping(price, special, clone, i), shopping(price, special, needs, i + 1));
+        } else {
+            return shopping(price, special, needs, i + 1);
+        }
+    }
+
+    public int dot(List<Integer> a, List<Integer> b) {
+        int sum = 0;
+        for (int i = 0; i < a.size(); i++) {
+            sum += a.get(i) * b.get(i);
+        }
+        return sum;
+    }
+}
