二叉搜索树的个数i

设值为n的情况下，可以组成f(n)个二叉搜索树，根据规律可知：

1. f(0) = 1
2. f(1) = 1
3. f(n) += f(k-1)*f(n-k), 其中k=1,2,...n

显然，这是一个动态规划问题，实现如👇：

//
// Created by jt on 2020/8/23.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param n int整型
     * @return int整型
     */
    int numTrees(int n) {
        // write code here
        vector<int> dp(n+1, 0);
        dp[0] = 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];
    }
};