1
# Runtime: 62 ms (Top 34.5%) | Memory: 18.09 MB (Top 39.7%)
2

3

4
class Solution:
5
    def soupServings(self, n: int) -> float:
6
        if n > 4451:
7
            return 1.0
8
        n = (n + 24) // 25
9
        memo = dict()
10

11
        def dp(i, j):
12
            if (i, j) in memo:
13
                return memo[(i, j)]
14
            if i <= 0 and j <= 0:
15
                return 0.5
16
            if i <= 0:
17
                return 1.0
18
            if j <= 0:
19
                return 0.0
20
            memo[(i, j)] = 0.25 * (
21
                dp(i - 4, j) + dp(i - 3, j - 1) + dp(i - 2, j - 2) + dp(i - 1, j - 3)
22
            )
23
            return memo[(i, j)]
24

25
        return dp(n, n)