96. Unique Binary Search Trees

Let F[j, i] be the number of unique binary search trees with root being j and total nodes being i. And let dp[i] be the number of unique binary search trees with total nodes being i. Since it is a binary search tree, we must have numbers [1, j-1] in the left subtree of root i and numbers [j+1, i] in the right subtree.

So for F[j, i], we have F[j, i] = dp[j-1]*dp[i-j], and thus for dp[i], we need to sum up F[j], where 1 <= j <=i. As a result, dp[i] = dp[0]*dp[i-1] + dp[1]*dp[i-2] + ... + dp[i-1]*dp[0].

1:  class Solution {  
2:  public:  
3:    int numTrees(int n) {  
4:      vector<int> dp(n+1, 0);  
5:      dp[0] = dp[1] = 1;  
6:      for (int i = 2; i <= n; i++) {  
7:        for (int j = 1; j <= i; j++) {  
8:          dp[i] += dp[j-1]*dp[i-j];  
9:        }  
10:      }  
11:      return dp[n];  
12:    }  
13:  };