美团一道经典面试算法题解法

这是美团一道经典面试算法题，在大三课上老师留给的一道课后练习，那么我们现在用Java来分析它的解法，此问题为斐波拉契数列（跳楼梯问题）

【问题描述】

一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。总共有多少种跳法？

【初步思路】

对于这一道算法题，我们首先可以做一个简单的分析：

当台阶为1级时，可以得知总共跳法为1种； 1

当台阶为2级时，可以得知总共跳法为2种； 1 1、2

当台阶为3级时，可以得知总共跳法为3种； 1 1 1、1 2、2 1

当台阶为4级时，可以得知总共跳法为4种； 1 1 1 1、1 1 2、1 2 1、2 2

但是当台阶来到5级时，它一共可以得到16种

由此可见我们可以使用递归推导出一个公式：f(1)=1;f(2)=1;f(n)=f(n-1)+f(n-2)；

【代码演示】

import java.util.Scanner;

public class Demo{
    
    public static int JumpFloor(int target) {
        if(target<1) return 0;
        else if (target==1) return 1;
        else return 2*JumpFloor(target-1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一个正整数");
        int target = sc.nextInt();
        System.out.println("得到的总种数为："+JumpFloor(target));
    }
}