Unique Binary Search Trees

Solution: 1:


class Solution {
public:
    int numTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int total = 0;
        if (n == 0)
            return 1;
        if (n == 1)
            return 1;
     
        for (int i = 1; i <= n ; i++) {
            total += numTrees(i - 1) * numTrees(n - i);
        }
        return total;
    }
};

DP Solution:

class Solution {
public:
    int numTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        //int total = 0;
       
        int total[n + 1];
        total[0] = 1;
        total[1] = 1;
        for (int i = 2; i < n+1; i++)
            total[i] = 0;
   
        for (int i = 2; i <= n; i++){
            for (int j = 1; j <= i; j++)
                total[i] += total[j-1] * total[i - j];
        }

        return total[n];
    }
};