dfs -> dp

808.soup-servings.py

# Time: O(n)
# Space: O(n)


# Before vs After 

#####################################
## Before
#####################################
 
# Time: O(1)
# Space: O(1)


class Solution(object):
    def soupServings(self, N):
        """
        :type N: int
        :rtype: float
        """
        m = {}
        if N > 5000: return 1 
        def serve(A, B):
            if (A, B) in m:
                return m[(A, B)]
            if A <= 0 and B > 0: return 1
            elif A <= 0 and B <= 0: return 0.5
            elif B <= 0: return 0
            m[(A, B)] = .25 * (serve(A-100, B) + serve(A -75, B-25) + serve(A-50, B-50) + serve(A-25, B-75))
            return m[(A, B)]
        return serve(N, N)

#####################################
## After
#####################################

class Solution(object):
    def soupServings(self, N):
        Q, R = divmod(N, 25)
        N = Q + (R > 0)
        if N >= 500: return 1

        memo = {}
        def dp(x, y):
            if (x, y) not in memo:
                if x <= 0 or y <= 0:
                    ans = 0.5 if x<=0 and y<=0 else 1.0 if x<=0 else 0.0
                else:
                    ans = 0.25 * (dp(x-4,y)+dp(x-3,y-1)+dp(x-2,y-2)+dp(x-1,y-3))
                memo[x, y] = ans
            return memo[x, y]

        return dp(N, N)