LeetCode: Unique Binary Search Trees

有经验了，一上来就知道用dp，一次过

 1 class Solution {
 2 public:
 3     int numTrees(int n) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         if (n < 2) return 1;
 7         vector<int> f(n+1, 0);
 8         f[0] = 1;
 9         f[1] = 1;
10         for (int i = 2; i <= n; i++) {
11             for (int j = 0; j < i; j++)
12                 f[i] += f[j]*f[i-1-j];
13         }
14         return f[n];
15     }
16 };

 1 public class Solution {
 2     public int NumTrees(int n) {
 3         if (n < 2) return 1;
 4         int[] f = new int[n+1];
 5         f[0] = f[1] = 1;
 6         for (int i = 2; i <= n; i++) {
 7             for (int j = 0; j < i; j++) {
 8                 f[i] += f[j] * f[i-1-j];
 9             }
10         }
11         return f[n];
12     }
13 }

View Code