动态规划

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k=in.nextInt();
        if(k<=2){
            System.out.println(1);
        }else{
            long a=1;
            long b=1;
            long c=0;
            for(int i=3;i<=k;i++){
                c=(a+b)%1000000007;
                b=a;
                a=c;
            }
            System.out.println(c);
        }

    }
}