JAVA算法题半递增序列个数

Question

一个 1 到 n 的排列被称为半递增序列，是指排列中的奇数位置上的值单调递增，偶数位置上的值也单调递增。

Answer 1

不要被题目骗了，其实这个问题就是n选n/2的组合问题，组合可以用杨辉三角推导，然后就是求余a=b+c=>a%k=(b%k+c%k)%k

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        System.out.println(main.getCombine(10000));
    }

    private int getCombine(int n){
        if(n==1)
            return 1;

        int k = n/2;
        int[] dp = new int[n+1];
        for(int i = 1; i <= n; i++){
            dp[0]=1;
            dp[i]=1;
            for(int j = i-1; j>=1; j--){
                dp[j]=dp[j-1]+dp[j];
                dp[j]%= (1e9+7);
            }
        }

        return dp[k];
    }
}