不同的二叉搜索树--dp解决

0x01.问题

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
输入示例：3
输出示例：5
解释：对于序列1，2，3，一共可以构成5种不同的二叉搜索树

C++函数形式为：     int numTrees(int n) 

0x02.简要分析

这个问题相当于给定一个长度为n的有序序列，求可能构成二叉搜索树的组合数。

我们看一个例子：

• 对于序列1,2,3,4,5,6,7,8,9，一共可以构成多少种二叉排序树？

对于构成二叉排序树来说，我们首先要选定根，根可以为多少呢？答案是序列里面的任意一个值，因为这是一个有序序列，不管如何选择，左边的都比它小（或没有左子树），右边的都比它大（或没有右子树），所以根节点的选择是任意的。

选择了根节点后，左右子树如何选择？其实左右子树也可以看作是一些子树的根，选择方法一样，所以，这就是个反复迭代的过程。

我们如何找到其中的迭代关系呢？

假设到9时，前面的组合数量都已经算出。现在选择5作为根，那么它的可能性应该是
左子树的可能性*右子树的可能性，左子树的可能性是多少呢？就是1,2,3,4产生的树的可能，右子树呢？就是6,7,8,9产生的树的可能，难道我们还要重新迭代一次左右子树嘛？
其实不必要，因为一个有序序列构成的种数，只和它的序列个数有关，和其它的无关，也就是说，左边四个元素，它产生的树就等于dp[4]，右边产生的也等于dp[4]，而根据动态规划的思想，我们假设前面的已经算出，那么这些就都是已知条件了。

所以，我们可以得到状态转移方程：

for(int j=1;j<=i;j++){
    dp[i]+=dp[i-1]*dp[i-j];
}

0x03.解决代码–动态规划

int numTrees(int n) {
    vector<int>dp(n+1,0);
    if(n<=1) return 1;
    dp[0]=1;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            dp[i]+=dp[j-1]*dp[i-j];
        }
    }
    return dp[n];
}

ATFWUS --Writing By 2020–03–26