Recursion+memoization


#1
def calc(left,right,i,dr,dl):
    r,l=0,0
    if dr[i][right]!=-1:
        r=dr[i][right]
    else:
        for j in range(i+1,right):
            r+=calc(i,right,j,dr,dl)
        dr[i][right]=r
    if dl[i][left+1]!=-1:
        l=dl[i][left+1]
    else:
        for j in range(left+1,i):
            l+=calc(left,i,j,dr,dl)
        dl[i][left+1]=l
    r=max(r,1)
    l=max(l,1)
    return r*l

class Solution:
    # @param A : integer
    # @return an integer
    def numTrees(self, A):
        dr=[]
        dl=[]
        for i in range(A+1):
            dr.append([-1]*(A+1))
            dl.append([-1]*(A+1))
        ans=0
        for i in range(A):
            res=calc(-1,A,i,dr,dl)
            ans+=res
        return ans