Question description

Screenshot 2016-10-06 15.59.15.png

My code

public class Solution {
    public int numTrees(int n) {
        int[] calculated = new int[n + 1];
        return helper(n, calculated);
    }
    
    public int helper(int n, int[] calculated) {
        if (n == 0) {
            calculated[0] = 1;
            return 1;
        }
        if (n == 1) {
            calculated[1] = 1;
            return 1;
        }
        if (calculated[n] != 0) return calculated[n];
        int ret = 0;
        
        for (int i = 0; i < n; i++) {
            ret += helper(i, calculated) * helper(n - i - 1, calculated);
        }
        calculated[n] = ret;
        return ret;
    }
}

Test result

Screenshot 2016-10-06 15.55.34.png

Solution

Use Catalan number. The formula is: h(n) = h(0)h(n-1)+h(1)h(n-2)+···+h(n-1)*h(0). (h(0) = 1, h(1) = 1)
However, when n is big (in LeetCode when n >= 19), the time performance is not acceptable. Thus, dynamic programming(DP) should be implemented. Use an array to record every calculated n. And when number i has to be calculated again, the program can directly get h(i) from calculated array.