Memoization slow but good to know


  • 0
    W

    Usually if you can write a solution using memoization, you can write it in DP since you know the recursive formula. DP usually runs faster than memoization.

    In memoization, you just simply store solutions to subproblems in cache, and once you encounter a bigger problem, you check the cahce first.

    I guess the only advantage of doing memoization is that it is easier to write. :p

    def minimumTotal(self, triangle): 
        d = dict()
        return min([self.helper(triangle, len(triangle)-1, k, d) for k in range(len(triangle))])
    
    def helper(self, triangle, i, j, d):
        if (i,j) in d:
            return d[(i, j)]
        if i == j == 0:
            d[(0,0)] = triangle[0][0]
            return triangle[0][0]
        left = self.helper(triangle, i-1, j-1, d) if i >= 1 and j >= 1 else float('inf')
        right = self.helper(triangle, i-1, j, d) if i >= 1 and j < len(triangle[i-1]) else float('inf')
        d[(i,j)] = min(left, right) + triangle[i][j]
        return d[(i,j)]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.