题解 | 跳台阶

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;
    }
}