题解 | 跳台阶
跳台阶
https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4
import java.util.*;
public class Solution {
/**
* 先求跳两级台阶最多的次数，对应跳一级台阶最少的次数，这个时候求一个组合数
* 接着减少跳两级台阶的次数，跳一级台阶的次数就增加 2，这个时候再求一个组合数
* 直到跳两级台阶的次数为 0，就一种组合
* 将以上所有组合数相加就是 结果
*/
public int jumpFloor(int number) {
int maxTwoJumpNum = number / 2;
int minOneJumpNum = number - maxTwoJumpNum * 2;
Long total = 0L;
for (int i = 0; i <= maxTwoJumpNum; i++) {
int oneJumpNum = minOneJumpNum + (maxTwoJumpNum - i) * 2;
total += countPermutations(i, oneJumpNum);
}
return total.intValue();
}
private Long countPermutations(int i, int j) {
int n = i + j;
if (i == 0 || j == 0) {
return 1L;
}
int min = Math.min(i, j);
Long factorialN = 1L;
Long factorialMin = 1L;
for (int k = 1; k <= min; k++) {
factorialN *= n - min + k;
factorialMin *= k;
}
return factorialN / factorialMin;
}
}
查看9道真题和解析