具有给定密钥的唯一BST数|动态规划-yiteyi-C++库

给定N，使用1到N之间的值查找可以生成的唯一BST的总数。 例如：

null

Input: n = 3 Output: 5For n = 3, preorder traversal of Unique BSTs are:1. 1 2 32. 1 3 23. 2 1 34. 3 1 25. 3 2 1Input: 4 Output: 14

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

在以前的讨论了O（n）后解决方案。在这篇文章中，我们将讨论一个基于动态规划的解决方案。对于i的所有可能值，将i视为根，然后[1…i-1 ]数字将落在左子树中，并且[i+n.n]数将落在右子树中。所以，在答案中加上（i-1）*（n-i）。乘积的总和将是唯一BST数的答案。以下是上述方法的实施：

C++

                         // C++ code to find number of unique BSTs                       
                         // Dynamic Programming solution                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find number of unique BST                       
                         int                                     numberOfBST(                                     int                                     n)                       
                         {                       
           
                                                 // DP to store the number of unique BST with key i                       
                                                 int                                     dp[n + 1];                       
                                                 fill_n(dp, n + 1, 0);                       
           
                                                 // Base case                       
                                                 dp[0] = 1;                       
                                                 dp[1] = 1;                       
           
                                                 // fill the dp table in bottom-up approach.                       
                                                 for                                     (                                     int                                     i = 2; i <= n; i++) {                       
                                                 for                                     (                                     int                                     j = 1; j <= i; j++) {                       
           
                                                 // n-i in right * i-1 in left                       
                                                 dp[i] = dp[i] + (dp[i - j] * dp[j - 1]);                       
                                                 }                       
                                                 }                       
           
                                                 return                                     dp[n];                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 3;                       
                                                 cout <<                                     "Number of structurally Unique BST with "                                     <<                       
                                                 n <<                                     " keys are : "                                     << numberOfBST(n) <<                                     ""                                     ;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java code to find number                       
                         // of unique BSTs Dynamic                       
                         // Programming solution                       
                         import                                     java.io.*;                       
                         import                                     java.util.Arrays;                       
           
                         class                                     GFG                       
                         {                       
                                                 static                                     int                                     numberOfBST(                                     int                                     n)                       
                                                 {                       
           
                                                 // DP to store the number                       
                                                 // of unique BST with key i                       
                                                 int                                     dp[] =                                     new                                     int                                     [n +                                     1                                     ];                       
                                                 Arrays.fill(dp,                                     0                                     );                       
           
                                                 // Base case                       
                                                 dp[                                     0                                     ] =                                     1                                     ;                       
                                                 dp[                                     1                                     ] =                                     1                                     ;                       
           
                                                 // fill the dp table in                       
                                                 // top-down approach.                       
                                                 for                                     (                                     int                                     i =                                     2                                     ; i <= n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j =                                     1                                     ; j <= i; j++)                       
                                                 {                       
           
                                                 // n-i in right * i-1 in left                       
                                                 dp[i] = dp[i] + (dp[i - j] *                       
                                                 dp[j -                                     1                                     ]);                       
                                                 }                       
                                                 }                       
           
                                                 return                                     dp[n];                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     n =                                     3                                     ;                       
                                                 System.out.println(                                     "Number of structurally "                                     +                       
                                                 "Unique BST with "                                     + n +                       
                                                 " keys are : "                                     +                       
                                                 numberOfBST(n));                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by shiv_bhakt.                       

Python3

                         # Python3 code to find number of unique                       
                         # BSTs Dynamic Programming solution                       
           
                         # Function to find number of unique BST                       
                         def                                     numberOfBST(n):                       
           
                                                 # DP to store the number of unique                       
                                                 # BST with key i                       
                                                 dp                                     =                                     [                                     0                                     ]                                     *                                     (n                                     +                                     1                                     )                       
           
                                                 # Base case                       
                                                 dp[                                     0                                     ], dp[                                     1                                     ]                                     =                                     1                                     ,                                     1                       
           
                                                 # fill the dp table in top-down                       
                                                 # approach.                       
                                                 for                                     i                                     in                                     range                                     (                                     2                                     , n                                     +                                     1                                     ):                       
                                                 for                                     j                                     in                                     range                                     (                                     1                                     , i                                     +                                     1                                     ):                       
           
                                                 # n-i in right * i-1 in left                       
                                                 dp[i]                                     =                                     dp[i]                                     +                                     (dp[i                                     -                                     j]                                     *                       
                                                 dp[j                                     -                                     1                                     ])                       
           
                                                 return                                     dp[n]                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 n                                     =                                     3                       
                                                 print                                     (                                     "Number of structurally Unique BST with"                                     ,                       
                                                 n,                                     "keys are :"                                     , numberOfBST(n))                       
           
                         # This code is contributed                       
                         # by Rituraj Jain                       

C#

                         // C# code to find number                       
                         // of unique BSTs Dynamic                       
                         // Programming solution                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                                 static                                     int                                     numberOfBST(                                     int                                     n)                       
                                                 {                       
           
                                                 // DP to store the number                       
                                                 // of unique BST with key i                       
                                                 int                                     []dp =                                     new                                     int                                     [n + 1];                       
                                   
                                                 // Base case                       
                                                 dp[0] = 1;                       
                                                 dp[1] = 1;                       
           
                                                 // fill the dp table in                       
                                                 // top-down approach.                       
                                                 for                                     (                                     int                                     i = 2; i <= n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 1; j <= i; j++)                       
                                                 {                       
           
                                                 // n-i in right * i-1 in left                       
                                                 dp[i] = dp[i] + (dp[i - j] *                       
                                                 dp[j - 1]);                       
                                                 }                       
                                                 }                       
                                                 return                                     dp[n];                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main ()                       
                         {                       
                                                 int                                     n = 3;                       
                                                 Console.Write(                                     "Number of structurally "                                     +                       
                                                 "Unique BST with "                                     + n +                       
                                                 " keys are : "                                     +                       
                                                 numberOfBST(n));                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by shiv_bhakt.                       

PHP

                         <?php                       
                         // PHP code to find number                       
                         // of unique BSTs Dynamic                       
                         // Programming solution                       
           
                         // Function to find number                       
                         // of unique BST                       
                         function                                     numberOfBST(                                     $n                                     )                       
                         {                       
           
                                                 // DP to store the number                       
                                                 // of unique BST with key i                       
                                                 $dp                                     =                                     array                                     (                                     $n                                     + 1);                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <=                                     $n                                     + 1;                                     $i                                     ++)                       
                                                 $dp                                     [                                     $i                                     ] = 0;                       
           
                                                 // Base case                       
                                                 $dp                                     [0] = 1;                       
                                                 $dp                                     [1] = 1;                       
           
                                                 // fill the dp table                       
                                                 // in top-down approach.                       
                                                 for                                     (                                     $i                                     = 2;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 for                                     (                                     $j                                     = 1;                                     $j                                     <=                                     $i                                     ;                                     $j                                     ++)                       
                                                 {                       
           
                                                 // n-i in right *                       
                                                 // i-1 in left                       
                                                 $dp                                     [                                     $i                                     ] += ((                                     $dp                                     [                                     $i                                     -                                     $j                                     ]) *                       
                                                 (                                     $dp                                     [                                     $j                                     - 1]));                       
                                                 }                       
                                                 }                       
           
                                                 return                                     $dp                                     [                                     $n                                     ];                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 3;                       
                         echo                                     "Number of structurally "                                     .                       
                                                 "Unique BST with "                                     ,                       
                                                 $n                                     ,                                     " keys are : "                                     ,                       
                                                 numberOfBST(                                     $n                                     ) ;                       
           
                         // This code is contributed                       
                         // by shiv_bhakt.                       
                         ?>                       

输出：

Number of structurally Unique BST with 3 keys are : 5

时间复杂性： O（n） ^2. )

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章