[DP/BackTracking]96. Unique Bina

• 分类：DP/BackTracking
• 时间复杂度: O(n)
• 空间复杂度: O(n)

96. Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

代码：

DP代码：

class Solution:
    def numTrees(self, n: 'int') -> 'int':
        
        if n<1:
            return 0
        
        dp=[0 for i in range(n+1)]
        dp[0]=1
        dp[1]=1
        for i in range(2,n+1):
            for j in range(i):
                dp[i]+=dp[j]*dp[i-j-1]
        
        return dp[-1]

记忆化递归代码：

class Solution:
    def numTrees(self, n: 'int') -> 'int':
        
        if n<1:
            return 0
        
        res=self.helper(n,{})
        
        return res
    
    def helper(self,n,memo):
        # 取出记忆
        if n in memo:
            return memo[n]
        
        # 设定出口
        if n==0 or n==1:
            return 1
        
        res=0
        for i in range(n):
            res+=self.helper(i,memo)*self.helper(n-1-i,memo)
            
        memo[n]=res
        return res

讨论：

1.所有booling和计数的题目都可以试着用记忆化递归求解
2.这道题还有个关键点是掌握树形结构的特征