leetcode

commit e352d7834c8b024e9f3c55ca4d10483220b8473b
parent f252679f199e006e0fe4dcb5856ad198decb181e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 29 Jul 2023 12:59:06 +0200

Daily Problem

Diffstat:
A
Problems/0808.cpp
 | 
17
+++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 18 insertions(+), 0 deletions(-)
diff --git a/Problems/0808.cpp b/Problems/0808.cpp
@@ -0,0 +1,17 @@
+class Solution {
+  double dp[200][200] = {0};
+
+  double calc(int a, int b) {
+    if (a <= 0 && b <= 0) return 0.5;
+    if (a <= 0) return 1;
+    if (b <= 0) return 0;
+    if (dp[a][b] > 0) return dp[a][b];
+    return dp[a][b] = 0.25 * (calc(a - 4, b) + calc(a - 3, b - 1) +
+                              calc(a - 2, b - 2) + calc(a - 1, b - 3));
+  }
+
+public:
+  double soupServings(int n) {
+    return n > 4800 ? 1.0 : calc(ceil(n / 25.0), ceil(n / 25.0));
+  }
+};
diff --git a/README.md b/README.md
@@ -360,6 +360,7 @@ for solving problems.
 |  0787  |   Medium   | [Cheapest Flights Within K Stops](Problems/0787.cpp)                                             |
 |  0797  |   Medium   | [All Paths From Source to Target](Problems/0797.cpp)                                             |
 |  0802  |   Medium   | [Find Eventual Safe States](Problems/0802.cpp)                                                   |
+|  0808  |   Medium   | [Soup Servings](Problems/0808.cpp)                                                               |
 |  0815  |    Hard    | [Bus Routes](Problems/0815.cpp)                                                                  |
 |  0830  |   Medium   | [Kth Smallest Element in a BST](Problems/0230.cpp)                                               |
 |  0837  |   Medium   | [New 21 Game](Problems/0837.cpp)                                                                 |