Leetcode 96 différents arbres de recherche binaires

leetcode96:Différents arbres de recherche binaires

Description du sujet

Pour vous donner un entier n ,Je vous en prie. n Les noeuds sont composés et les valeurs des noeuds sont de 1 À n Différents Arbre de recherche binaire Combien de？Renvoie le nombre d'arbres de recherche binaires qui répondent à l'intention du sujet.

Exemple d'entrée / sortie

Entrée：n = 3
Produits：5

Entrée：n = 1
Produits：1

Algorithme I：Utiliser la planification dynamique

    //Définition de l'arbre de recherche binaire：Si son Sous - arbre gauche n'est pas vide,La valeur de tous les noeuds du sous - arbre gauche est inférieure à son noeud racine,Si son Sous - arbre droit n'est pas vide,La valeur de tous les noeuds du sous - arbre droit est supérieure à la valeur de son noeud racine
   //Ses sous - arbres gauche et droit sont également des arbres de recherche binaires 
    int numTrees(int n)
    {
    
        //Créer un tableau de planification dynamique
        vector<int>dp(n+1,0);
        //Définir les conditions initiales
        dp[0]=1;
        dp[1]=1;
        //Définir l'équation de conversion
        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];
    }

Algorithme 2：Utiliser la définition du nombre de glandes

//Nombre de catalans
    int numTrees2(int n)
    {
    
        long long c=1;
        for(int i=0;i<n;i++)
        {
    
            c=c*2*(2*i+1)/(i+2);
        }
        return (int)c;
    }