LeetCode – Refresh – Unique Binary Search Tree

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