808.md

808. Soup Servings

Solution 1 (time O(n^2), space O(n^2))

# Dynamic programming
class Solution(object):
    def soupServings(self, n):
        """
        :type n: int
        :rtype: float
        """
        n = min(200, int(math.ceil(n / 25.0)))
        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
        dp[0][0] = 0.5
        for j in range(1, n + 1):
            dp[0][j] = 1
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dp[i][j] = (dp[max(i - 4, 0)][j]
                            + dp[max(i - 3, 0)][max(j - 1, 0)]
                            + dp[max(i - 2, 0)][max(j - 2, 0)]
                            + dp[max(i - 1, 0)][max(j - 3, 0)]) / 4.0
        return dp[n][n]