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 一般只求结果的数量而不要求所有可能的解就可能用DP来解决了，f[i][j] = sum(f[i][k-1] * f[k+1][j]); i <= k <= j

1 class Solution { 2 private: 3     int f[1000][1000]; 4 public: 5     int getF(int beg, int end) 6     { 7         if (beg > end) 8             return 1; 9             10         return f[beg][end];11     }12     13     int numTrees(int n) {14         // Start typing your C/C++ solution below15         // DO NOT write int main() function16         for(int i = 0; i < n; i++)17             f[i][i] = 1;18             19         for(int len = 2; len <= n; len++)20             for(int beg = 0; beg < n; beg++)21             {22                 int end = beg + len - 1;23                 if (end >= n)24                     break;25                 26                 f[beg][end] = 0;27                 for(int mid = beg; mid <= end; mid++)28                     f[beg][end] += getF(beg, mid - 1) * getF(mid + 1, end);29             }30             31         return f[0][n-1];32     }33 };