96_不同的二叉搜索树.py

'''
题目描述:
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

解题思路：
DP：
    设
    F(i,n)表示长度为n的序列，第i个平衡二叉树的个数
    G(n)表示 长度为n的序列的不同二叉搜索树个数
        则G(n)=sum(F(i,n))(i=1,2,...,n)(n是确定值)
    又对于每个位置i的F(i,n)有：
        F(i,n)=G(n-i)*G(i-1)(左右子树的排列组合)(n是确定值)
    故：
        G(n)=sum(G(n-i)*G(i-1))(i=1,2,..,n)
        举例说明：
        当n=2时：
        G(2)=sum(G(2-i)*G(i-1))(i=1,2)
            =G(2-1)*G(1-1)+G(2-2)*G(2-1)
            =G(1)*G(0)+G(0)*G(1)
        (由此可由之前的状态推导出当前的状态，即可通过DP优化)
    
    base case:
        G(0)=1,G(1)=1

'''


class Solution:
    def numTrees(self, n: int) -> int:
        G=[0]*(n+1)
        #base_case
        G[0]=1
        G[1]=1
        for i_n in range(2,n+1):
            #易错点：j==从1到i_n+1
            for j in range(1,i_n+1):
                G[i_n]+=G[j-1]*G[i_n-j]
        return G[n]