题目描述

原题链接：96. 不同的二叉搜索树

解题思路

动态规划五部曲：

（1）dp[i]的含义： 从1到i为节点，可以组成BST的数量

（2）递推公式： dp[i] += dp[j - 1] * dp[i - j]，根据已有的数学结论，当以数字i为根节点时，左子树会有以j - 1为头结点的BST个数，右子树会有i - j为头结点的BST个数，此时的共有的情况就是左子树个数 * 右子树个数，左子树从0到i - 1依次遍历，求和得到总情况个数。

（3）dp数组初始化： dp[0] = dp[1] = 1，以1为根节点和以0为根节点（空树）的BST仅有一种情况。

（4）遍历顺序： 从小到大。

（5）举例：

class Solution {
public:
    int numTrees(int n) {
        int dp[20] = {0};
        dp[0] = dp[1] = 1;        
        for(int i = 2; i <= n; i++) {				// 注意这里初始化dp到1即可，不能直接初始化dp[2]，因为遍历的时候可能n只有一个1
            for(int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
};

参考文章：96. 不同的二叉搜索树、不同的二叉搜索树