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.
