Leetcode 96-不同的二叉搜索树

本题的题面如下：给定一个整数 n，求以 1 ...n为节点组成的二叉搜索树有多少种？

思考过程：

首先很容易想到，只有一个结点的时候，二叉搜索树只有一种。而有多个结点的时候，根节点的左右子树还是二叉搜索树。我们令n个结点的二叉搜索树的二叉搜索树的种数为 $dp[n]$ 。假设根节点的值为i,则左子树的结点为1至i-1,右子树的结点为i+1至n。显然，根节点为i的有n个结点的二叉搜索树的个数为 $dp[i-1]*dp[n-i]$ 。那么显然，结点数为n的二叉搜索树的个数为 $\sum_{i=1}^n dp[i-1]*dp[n-i]$ .

代码如下：


class Solution {

public:

    int dp[1000];

    int numTrees(int n) {

        memset(dp,0,sizeof(dp));

        dp[0]=1;

        dp[1]=1;

        for(int i = 2;i<=n;i++)

        {

            int sum = 0;

            for(int j = 0;j<i;j++)

            {

                sum += dp[j]*dp[i-j-1];

            }

            dp[i]+=sum;

        }

        return dp[n];

    }

};