Given n, how many structurally unique BST‘s (binary search trees) that store values 1 ... n?
Example:
Input: 3
Output: 5
Explanation:
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 class Solution { 2 public: 3 vector<int>q; 4 int _numTrees(int n) { 5 if (q[n] != -1)return q[n]; 6 int ans = 0; 7 for (int i = 1; i <= n; i++) 8 ans += _numTrees(i - 1) * _numTrees(n - i); 9 q[n] = ans; 10 return ans; 11 } 12 int numTrees(int n) { 13 q=vector<int>(n+1,-1); 14 q[1] = 1; q[0] = 1; 15 return _numTrees(n); 16 } 17 };
可以用dp
19.2.27 [LeetCode 96] Unique Binary Search Trees
原文：https://www.cnblogs.com/yalphait/p/10445781.html
