LeetCode 96 Unique Binary Search Tree(Python詳細および実装)

【テーマ】
Given an integer n, generate allstructurally unique BST's (binary search trees) that store values 1...n.
 
For example,
Given n = 3, your program should return all5 unique BST's shown below.
 
  1         3     3     2      1
   \      /    /     /\     \
    3     2     1     1   3      2
   /    /      \                \
  2     1         2                 3
この問題は94問題と類似しており、94問題は条件に合致する二叉木の木を求め、この問題はすべての条件に合致する二叉木を返す.
【考え方】
動的計画の解:
問題の状態遷移方程式はどのように求めますか?ほとんどの動的計画の難点は状態遷移方程式を求めることである.
n=0の場合、空のツリー、---->dp[0]=1;
n=1の場合、dp[1]=1;
n=2の場合、dp[2]=2;
n>2の場合、dp[n]=dp[0]*dp[n-1]+dp[1]*dp[n-2]+......+dp[n-1]*dp[0];
【Python実現】
#動的計画反復解

class Solution(object):
   def numTrees(self, n):
       """
       :type n: int
       :rtype: int
       """
       dp = [1, 1, 2]
       if n < 3: return dp[n]
       dp += [0 for i in range(n-2)]
       for i in range(3, n+1):
           for j in range(i):
                dp[i] += dp[j]*dp[i-j-1]
       return dp[n]
if __name__ == '__main__':
    S= Solution()
   res = S.numTrees(3)
   print(res)   

   
#再帰解

class Solution(object):
   def numTrees(self, n):
       """
       :type n: int
       :rtype: int
       """
       dp = [1, 1, 2]
       if n < 3: return dp[n]
       ans = 0 
       for i in range(n): 
           ans += self.numTrees(i)*self.numTrees(n-i-1) 
       return ans
 
 
if __name__ == '__main__':
    S= Solution()
   res = S.numTrees(3)
   print(res)