形成山脉的方式的数量
Number of ways to form a mountain ranges
我正在查看加泰罗尼亚数字的应用程序:
形成 n 个向上笔划和 n 个向下笔划的“山脉”都保持在原始线上方的方式的数量。
现在给定一个数字 n,求山脉的数量。
public int countMountainRanges(int n) {
}
我们这里可以用什么逻辑或者公式来得到输入的路数n
。
我尝试了公式 F(n) = F(n-1) + F(n-2),但在这种情况下不起作用。
F(n) = F(n-1) + F(n-2)
是第n个斐波那契数的公式。另一方面,第 n 个加泰罗尼亚语数由 (2n 选择 n) / (n + 1) 给出。
public static int countMountainRanges(int n) {
return choose(2 * n , n) / (n + 1);
}
private static int choose(int n, int k){
int res = 1;
k = Math.min(k, n - k);
for (int i = 0; i < k; i++) {
res = res * (n - i) / (i + 1);
}
return res;
}
我正在查看加泰罗尼亚数字的应用程序:
形成 n 个向上笔划和 n 个向下笔划的“山脉”都保持在原始线上方的方式的数量。
现在给定一个数字 n,求山脉的数量。
public int countMountainRanges(int n) {
}
我们这里可以用什么逻辑或者公式来得到输入的路数n
。
我尝试了公式 F(n) = F(n-1) + F(n-2),但在这种情况下不起作用。
F(n) = F(n-1) + F(n-2)
是第n个斐波那契数的公式。另一方面,第 n 个加泰罗尼亚语数由 (2n 选择 n) / (n + 1) 给出。
public static int countMountainRanges(int n) {
return choose(2 * n , n) / (n + 1);
}
private static int choose(int n, int k){
int res = 1;
k = Math.min(k, n - k);
for (int i = 0; i < k; i++) {
res = res * (n - i) / (i + 1);
}
return res;
}