Leetcode 96/dynamic-programming/

直达：https://leetcode.com/problems/unique-binary-search-trees/description/

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

For example,
Given n = 3, there are a total of 5 unique BST's.

中文描述：输入一个数字n ，n能组成几种不同排列的搜索二叉树（左<中心<右）。如图所示，输入3,有5中可能性。

题解：本题归为动态规划，往往有递推的思路，如何从之前的结果得到现在的结果

1. 搜索二叉树，首先考虑，1....i。如果以1或者i为根节点，加入以i为根，数列又变成了1...(i-1)相当于求dp(i-1)，所以各有dp(i-1)种情况；
2. 如果以2...(i-1)之间的任意一个数字为跟，假设根节点为2, 2的左子树为1, 2的右子树为3...(i),分别具有的情况为d(1)与d(i-2)，总和为d(1)*d(i-2)。而以3为根节点，情况相同，为d(2)d(i-3);这样可以得到递推式子：

f(n) = f(n-1) + f(n-2)f(1) + f(n-3)f(2) + … + f(1)f(n-2) + f(n-1)

代码：
java

    public static int numTrees(int n) {//#96 
        if(n==1) return 1;
        if(n==2) return 2;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3;i<=n;i++){
            for(int j=1;j<=i-2;j++){
                dp[i] += dp[j]*dp[i-j-1];
            }
            dp[i] += dp[i-1]*2;
        }
        return dp[n];
    }

python3

    def numTrees(self,n):
        if(n==1): 
            return 1
        if(n==2):
            return 2
        else:
            dp = [0,1,2]
            for i in range(3,n+1):
                temp = dp[i-1]*2
                for j in range(1,i-1):
                    temp += dp[j]*dp[i-j-1]
                dp.append(temp)
            return dp[n]

批注：
本题为卡特兰数，推荐知乎上看到的一个神奇的网站，http://oeis.org/，输入一组数，系统可以自动帮助你得到这是什么类型的数。另外“卡特兰数“变种题目还有，此为一种类型，以后遇到了总结。

Ending.