题解 | #不同的二叉搜索树(一)#

动态规划 dp[i]表示i个节点对应的二叉搜索树个数

考虑边界的情况，即0个节点和1个节点的情况，那么构建的二叉搜索树只能是空树或只有根节点的树

转移方程：当前节点为i时，那么从[1,i]中的每个数都可以作为根节点，假设当前取j∈[1,i]为根节点，由于是构建二叉搜索树，那么左子树的节点只能选[1,j-1]范围的数，右子树只能选取[j+1，i]范围内的数。构建的时候只有左右子树节点个数有关

构建搜索二叉树的时候，根节点为j的所有可能的情况为 左子树的情况数(dp[i-1])✖右子树的情况数(dp[i-(j+1)+1]  ---> dp[i-j])。而节点个数为i的情况下所能构建的二叉搜索树的情况总数为每个节点作为根节点的情况数之和。

public class Solution {
    public int BSTCount (int n) {
        // write code here
        if(n < 2)
            return n;
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for(int i=2;i<=n;i++){
            int ans = 0;
            // 枚举每个节点作为根节点
            for(int j=1;j<=i;j++){
                ans += dp[j-1]*dp[i-j];
            }
            dp[i] = ans;
        }
        return dp[n];
    }
}