leetcode_96

发表于   |   分类于

Unique Binary Search Trees

题目戳这

题意

给定一个n，求1-n能够形成不同BST形态的个数。

解法

这题记得是卡特兰数的规律，所以直接上公式就可以。

但是这个用dp思想推导的过程也是很精彩的。

假如我们用f(i,n)表示以i为根节点，n个数字能够形成BST的个数。g(n)表示n个数字能够形成的BST个数。
则g(n) = f(1,n)+f(2,n)+f(3,n)+…..f(n,n)

那么f(i,n)能够怎么推导呢？比如f(3,7),说明以3为根节点，7个数字形成的BST数量，那么左右子树的序列为1-2和4-7，则根据g(n)的定义，左右子树序列能够形成的BST数量为g(2)g(4),也就是说f(3,7)=g(2)\g(4),再抽象成公式就是

f(i,n) = g(i-1)*g(n-i)。
而g(n) = f(1,n)+f(2,n)+…f(n,n)的

所以g(n) = g(0)*g(n-1)+g(1)*g(n-2)+….+g(n-1)*g(0)
，最后输出g(n).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        # cur = 1
        
        # if n <= 1:
        #     return 1
        
        # for i in range(2,n+1):		# catlant
        #     cur = cur*(4*i-2)/(i+1)
        
        # return cur
        
        G = [0]*(n+1)
        G[0] = G[1] = 1
        
        for i in range(2,n+1):
            for j in range(1,i+1):
                G[i] += G[j-1] * G[i-j]
        
        return G[n]