LC96 题解 | #不同的二叉查找树#

dp：本题把问题划分分成左子树和右子树两部分子问题

动归五部曲：

1. 确定dp[i]的含义：dp[i]表示由i个节点构成的二叉查找树，共有dp[i]种不同的结构
2. 初始化：
1. dp[0] = 1，空树也是二叉查找树，并且只有一种结构
2. dp[1] = 1，单节点就一种结构
3. dp[2] = 2
3. 递推公式：dp[i] = 左子树的结构数 * 右子树的结构树。左子树和右子树的结构树都是收到他们各自的节点个数的影响的，那么左右子树的节点个数受什么影响呢？

二叉查找树的左子树的所有节点小于root，右子树的所有节点大于root，因此左右子树各自的节点个数是由root的大小决定的。而root不同，二叉树的结构也不同，所以我们在计算dp[i] 的时候不光要计算“左子树的结构数 * 右子树的结构树”，还要把所有root的情况都加起来。那么就需要另一层for循环，遍历在当前i个节点构建树的情况下，谁来当root。

eg：有10个节点，dp[10]就是有十个节点1...10。那么在1当root的时候dp[10]的左子树就是dp[0]，右子树就是dp[9]....4当root的时候左子树就是dp[3]，右子树就是dp[6]，以此类推。

最后注意求dp[i]的时候是“+=”加等，不解释。

class Solution {
    
    public int numTrees(int n) {
        if (n < 2) return n;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        // 外层循环控制树中有多少个节点
        for (int i = 2; i < n + 1; ++i) {
            // 内层循环中的j控制第几个节点当root（题目中的下标从1开始）
            // 因为是BST，左边就是j-1个节点，右边就是i - j个节点
            // 左边j-1个节点有dp[j-1]种可能，右边i-j个节点有dp[i-j]种可能
            // 所以相乘，则有递推公式dp[i] += dp[j-1] * dp[i-j]
            // 解释：
            // dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
            for (int j = 1; j <= i; ++j) {
                dp[i] += dp[j-1] * dp[i-j];
            }
        }  
        return dp[n];
    }
}