这些小活动你都参加了吗?快来围观一下吧!>>
电子产品世界 » 论坛首页 » 嵌入式开发 » STM32 » unique-binary-search-trees

共1条 1/1 1 跳转至

unique-binary-search-trees

高工
2018-01-12 12:48:28     打赏

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3



题意:统计1到n能构成二叉搜索树的个数

思路:

动态规划

以i为跟几点的数,左子树由[0, i-1]构成,其右子树由[i+1, n]构成


[cpp] view plain copy
  1. class Solution  

  2. {  

  3. public:  

  4.     int numTrees(int n)  

  5.     {  

  6.         if (n<0)  

  7.         {  

  8.             return -1;  

  9.         }  

  10.           

  11.         vector<int> dp(n+1, 0);  

  12.         dp[0] = 1;  

  13.         dp[1] = 1;  

  14.   

  15.         for (int i=2; i<=n; i++)  

  16.         {  

  17.             for (int j=0; j<i; j++)  

  18.             {  

  19.                 dp[i] += dp[j] * dp[i - j - 1];  

  20.             }  

  21.         }  

  22.   

  23.         return dp[n];  

  24.     }  

  25. }; 




共1条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]