leetcode刷题：动态规划07（不同的二叉搜索树）

96.不同的二叉搜索树

力扣题目链接

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

没做出来，研究题解最后做出来了。思路很简单。
当前dp[ i ]的值为以本树所有结点的每个结点都做一次头结点，左子树和右子树变化的乘积为总和， 比如以 j 为根结点，则比 j 小的数组成的左子树，有 j - 1 个数，也就是dp[ j - 1 ]种组合，比 j 大的数，一共 i - j 个，则右子树的数字有 i - j 个，共 dp [ i - j ]种变化。左右相乘，为当前 j 为结点的总变化，所有的总变化就是每个数都当一次头结点，所变化之和。

package com.programmercarl.dynamic;

/** * @ClassName NumTrees * @Descriotion TODO * @Author nitaotao * @Date 2022/7/25 17:00 * @Version 1.0 * https://leetcode.cn/problems/unique-binary-search-trees/ * 96. 不同的二叉搜索树 **/
public class NumTrees {
    
    public int numTrees(int n) {
    
        /** * 二叉搜索树，升序 * n>=1 */
        if (n <= 2) {
    
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
    
            // n>=1
            for (int j = 1; j < i; j++) {
    
                //dp[i]的每种可能性为以其中一个数为头结点，左子树的变法*右子树的变法
                // 以 dp[j]为头结点
                //左子树有j-1个 右子树有i-j个
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}