CatalanNumbers.java

public class CatalanNumbers {
    public int numPatterns(int n) {
        double count = 1.0;
        for (double i = 1.0; i <= n; i += 1.0) {
            count *= ((i + n) / i);
        }
        return (int) Math.round(count / (n + 1));
    }

    public int numPatternsDP(int n) {
        long[] memo = new long[n+1];
        memo[0] = memo[1] = 1;
        for (int i = 2; i <= n; i++) {
            memo[i] = 0;
            for (int j = 0; j < i; j++) {
                memo[i] += memo[j] * memo[i-j-1];
            }
        }
        return (int)memo[n];
    }
}