Skip to content

Instantly share code, notes, and snippets.

@yokolet
Created September 8, 2019 22:33
Show Gist options
  • Save yokolet/f33be1919df2015a172fd3c80f89aaef to your computer and use it in GitHub Desktop.
Save yokolet/f33be1919df2015a172fd3c80f89aaef to your computer and use it in GitHub Desktop.
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];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment