808.md

808 Soup Servings

Description

link

---

Solution (DFS)

dp[a][b] : the propability of situation that A is a ml and B is b ml

Recursive : dp[a][b] = dp[a - 100][b] + dp[a - 75][b - 25] + dp[a - 50][b - 50] + dp[a - 25][b - 75] (suit for dfs)

be careful of the border judge, and when N > 4800, just return 1

---

Code

Complexity T : O(n^2) M : O(n^2)

class Solution:
    def soupServings(self, N):
        """
        :type N: int
        :rtype: float
        """
        memo = {}
        
        def dfs(a, b):
            if (a, b) in memo:
                return memo[(a, b)]
            if a <= 0 and b <= 0:
                res = 0.5
            elif a <= 0:
                res = 1
            elif b <= 0:
                res = 0
            else:
                res = 0.25 * (dfs(a - 100, b) + dfs(a - 75, b - 25) + dfs(a - 50, b - 50) + dfs(a - 25, b - 75))
            memo[(a, b)] = res
            return res
        
        if N > 4800:
            return 1
        return dfs(N, N)