题面

楼梯一共有 n层台阶。因为腿长的限制,每次最多能上 4 层台阶。 但是第 5,7 层楼梯坏掉了不能踩。求上楼梯的方案数。n>8

输入

输入n

输出

输出上楼梯的方案总数

样例输入

10

样例输出

72

代码

import java.util.Scanner;

public class Main {
    public static int pa(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 4;
        if(n == 4) return 8;
        if(n == 5 || n == 7) return 0;
        return pa(n - 1) + pa(n - 2) + pa(n - 3) + pa(n - 4);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = pa(n);
        System.out.println(ans);

    }
}

立志做一名攻城狮