Create soup-servings.cpp

kamyu104 · web-flow · commit 62e19d02a319 · 2018-04-01T21:16:17.000+08:00
diff --git a/C++/soup-servings.cpp b/C++/soup-servings.cpp
@@ -0,0 +1,46 @@
+// Time:  O(1)
+// Space: O(1)
+
+class Solution {
+private:
+    template <typename T>
+    struct PairHash {
+        size_t operator()(const pair<T, T>& p) const {
+            size_t seed = 0;
+            seed ^= std::hash<T>{}(p.first)  + 0x9e3779b9 + (seed<<6) + (seed>>2);
+            seed ^= std::hash<T>{}(p.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
+            return seed;
+        }
+    };
+    
+public:
+    double soupServings(int N) {
+        if (N > 4800) {
+            return 1.0;
+        }
+        unordered_map<pair<int, int>, double, PairHash<int>> lookup;
+        N = (N + 24) / 25;
+        return dp(N, N, &lookup);
+    }
+    
+private:
+    double dp(int a, int b, unordered_map<pair<int, int>, double, PairHash<int>> *lookup) {
+        if (lookup->count(make_pair(a, b))) {
+            return (*lookup)[make_pair(a, b)];
+        }
+        if (a <= 0 && b <= 0) {
+            return 0.5;
+        }
+        if (a <= 0) {
+            return 1.0;
+        }
+        if (b <= 0) {
+            return 0.0;
+        }
+        (*lookup)[make_pair(a, b)] = 0.25 * (dp(a - 4, b, lookup) +
+                                             dp(a - 3, b - 1, lookup) +
+                                             dp(a - 2, b - 2, lookup) +
+                                             dp(a - 1, b - 3, lookup));
+        return (*lookup)[make_pair(a, b)];
+    }
+};
