这道题目，个人认为非常经典，虽然看到题目要求计算不同BST个数，一般会联想到动态规划，但动态规划如何求解递推方程成为了最大的难点。
在之前的题目中我们解决了台阶问题，递推方程相对简单:
定义f(n)表示走到第n台阶可能的走法（每次可以走一个台阶或者两个台阶），那么递推方程：
f(n)=f(n-1)+f(n-2)表示走到第n台阶走法等于走到第n-1台阶的走法加上走到n-2台阶的走法。
而96这道题相对没有那么好写递推公式。
显而易见对这道题目而言DP[n]表示数字n对应不同BST数目，dp[0]=dp[1]=1
dp[2]推导方法为：1 2都可以为根节点：
当1为根节点时左子树为DP[0],右子树为DP[1].
当2为根节点时左子树为DP[1],右子树为DP[0].
递推公司 DP(n) = DP(0) * DP(n-1) + DP(1) * DP(n-2) + … + DP(n-1) * DP(0)
详细解释可以学习youtube
代码实现：

class Solution {
public:
    int numTrees(int n) {
        vector<int> res(n + 1,0);
        res[0] = 1;
        res[1] = 1;
        
        for(int i = 2;i <= n;i++)
        {
            for(int j = 0;j < i;j++)
                res[i] += res[j]*res[i-j-1];
        }
        
        return res[n];
    }
};