首页 > 代码库 > 【leetcode】 Unique Binary Search Trees (middle)☆
【leetcode】 Unique Binary Search Trees (middle)☆
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
思路：因为是奔着动态规划强化来做的，所以方法肯定是动态规划。而且题目里连个树的定义都没给，肯定不用真的把树建出来。
首先说明下面我的思路是个很烂的思路，但是AC了
设f[a][b]表示若以c为头结点，有a个小于c的数和b个大于c的数时 可以表示的方式数，则
f[a][b + 1] = f[a][0]*(f[0][b] + f[1][b-1] +...+f[b-1][1] + f[b][0])
f[0][0] = 1
f[0][1] = 1
f[a][b] =f[b][a]
#include <iostream>#include <vector>#include <algorithm>#include <queue>#include <stack>using namespace std;class Solution {public: int numTrees(int n) { if(n == 0 || n == 1) { return n; } //f[a][b]表示若以c为头结点，有a个小于c的数和b个大于c的数时 可以表示的方式数 vector<vector<int> > f(n, vector<int>(n, 0)); f[0][0] = 1; f[0][1] = 1; f[1][0] = 1; for(int total = 3; total <= n; total++) { int less = (total - 1) / 2; for(int i = less; i >= 0; i--) { int ways = 0; int large = total - 1 - i; for(int j = 0; j <= large - 1; j++) { ways += f[j][large - j - 1]; } ways *= f[i][0]; f[i][large] = ways; f[large][i] = ways; } } int ans = 0; for(int i = 0; i < n; i++) { ans += f[i][n - 1 - i]; } return ans; }};int main(){ Solution s; int ans = s.numTrees(3); return 0;}
看别人的思路，发现自己傻×了。
idea: choose i to be the root, then there i -1 numbers in the left child tree, n - i numbers in the right child tree, calculate child tree recursively
f(0) = 1
f(1) = 1
f(2) = 2
f(n) = f(n-1) * f(0) + f(n-2) * f(1) + f(n-3) * f(2) + ... + f(0) * f(n-1)
int numTrees(int n) { if(n<0) return 0; vector<int> result; result.push_back(1); result.push_back(1); for(int k=2;k<=n;k++) { int sum=0; for(int i=1;i<=k;i++) { sum+=(result[i-1]*result[k-i]); } result.push_back(sum); } return result[n];}
还有用数学方法的： Catalan number C(i+1) = C(i) * 2 * ( 2 * i - 1 ) / (i + 1);
class Solution {public: int numTrees(int n) { long long ans = 1; for(int i = 1; i <= n; ++ i) ans = ans * 2 * (2 * i - 1) / (i + 1); return (int) ans; }};
【leetcode】 Unique Binary Search Trees (middle)☆