DFS Fastest Solution with python


  • 0
    class Solution(object):
        def numTrees(self, n):
            """
            :type n: int
            :rtype: int
            """
            cache={0:1,1:1,2:2,3:5,4:14}
            def dp(n):
                if n in cache:return cache[n]
                
                t=0
                l,r=0,n-1
                for i in range(n):
                    t+=dp(l)*dp(r)
                    #print n,t
                    l+=1;r-=1
                cache[n]=t
                return t
            #print cache
            return dp(n)
    

Log in to reply
 

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