#96 Unique Binary Search Trees——Top 100 Liked Questions

ゝ一世哀愁。 2022-01-23 06:13 119阅读 0赞

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

> 第一次：卡特兰数问题：
> 
>     class Solution(object):
>         def numTrees(self, n):
>             """
>             :type n: int
>             :rtype: int
>             """
>             #f(0) = 1
>             #f(1) = 1
>             #f(2) = f(1)f(0)+f(0)f(1)
>             #f(3) = f(2)f(0)+f(1)f(1)+f(0)f(2)
>             dp = [0] * (n+1)
>             dp[0], dp[1] = 1, 1
>             for i in range(2,n+1):
>                 for j in range(i):
>                     dp[i] += dp[j] * dp[i-1-j]
>             return dp[-1]
> 
> Runtime: 12 ms, faster than 97.42% of Python online submissions forUnique Binary Search Trees.
> 
> Memory Usage: 11.8 MB, less than 40.92% of Python online submissions for Unique Binary Search Trees.

类似问题都可以用这个程序：

①n对括号的正确匹配数目：

n=1:()  f(1)=1

n=2:()()    (())   f(2)=2

n=3:()()()  (())()  ((())) ()(())  (()())   f(3)=5

思路：把它想象成01问题，考虑任意一种配对方案，最后一个为右括号，记为1，其前面如果没有1，则至少有1个0，如果前面有1，则0的个数大于1的个数

②n个元素，进出栈的方式有多少种：进栈为0，出栈为1，0的个数一定要大于等于1的个数

③买票找零问题：16个人按顺序去买票，票价为50元，其中8个人每人身上只有一张50块钱，另外8个人每人身上只有一张100块钱。求要在售票员没有初始金钱的情况下顺利购票的排队方案：带50块钱的人数要大于等于带100块钱的人数

④照相排队问题：12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种：0表示出现在第一排的人，1表示出现在第二排的人，，看作长度为12的01序列，0的数量总是大于等于1的数量

⑤凸多边形三角划分问题：凸多边形的边数n，通过若干条互不相交的对角线，把这个多边形划分成了多少个三角形

⑥在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数

⑦N\*N棋盘单调路径问题：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？