算法学习——递推之猴子爬山

算法描述

一个猴子沿着一座山的n级台阶向上爬，猴子上山一步可跳1级或3级，试求上山的n级台阶有多少种不同的爬法

算法思路

利用递推的思想，猴子在第n级台阶上，它之前可能在第n-1级台阶上或者是在n-3级台阶上，由此可得到递推的公式

f(n)代表着n级台阶共有的爬法

f(1) = 1

f(2)= 1

f(3) =2 三步，每一步都是跳1级台阶 走了一步，一步跳3级

f(n)=f(n-1)+f(n-3) (n>3)

算法实现

    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    scanner.close();
    long[] k = new long[10000];
    k[1]=1;
    k[2]=1;
    k[3]=2;

    for(int i=4;i<=n;i++){
        k[i]=k[i-1]+k[i-3];
    }
    System.out.println(k[n]);

结果