青蛙跳台阶

文字表述
首先，当只有一级台阶时，毫无疑问，只有一种跳法

其次，当有两级台阶时，就是两种跳法

那么，三级台阶时，应该两种情况

1、若青蛙先跳一级台阶，接下来就有两种跳法，要么一级一级地跳，要么直接就跳上两级

2.若青蛙先跳两级台阶，接下来只能在再跳一级台阶

所以当有三级台阶时，一共有3种跳法

那么，一共有4级台阶时，一共有多少种跳法呢？

我们不妨列举一下

1.青蛙先跳一级台阶，接下来他就会还有3级台阶要去跳，而这3级台阶不就是上面3级台阶的重复吗！所以此时一共有3种跳法

2.青蛙先跳2级台阶，接下来他还有2级台阶要跳，此处也可以使用之前得出的2级台阶的结果，所以此时一共有2种跳法

所以当青蛙要跳4级台阶时，其实就是跳3级台阶的跳法加上跳2级台阶的跳法

总结：事实上，跳n级台阶的跳法就是跳n-1级台阶的跳法加上n跳-2级台阶的跳法，而这就可以使用递归的方法来解决

图片表述
image-20220404165202728

跳一级就只有一种跳法

image-20220404165242177

跳两级有2种跳法也是非常好理解的

image-20220404170004929

当有3级台阶时，可能会稍微复杂一点

image-20220404170100754

所以当有3级台阶时，一共有3种方法（其实就是有1级台阶和有两级台阶的跳法之和）

当有4级台阶时，其实也就是3级台阶和2级台阶的跳法之和

所以，要求有n级台阶时的跳法，其实就是n-1级台阶与n-2级台阶的跳法之和

代码如下:

public class Solution {

public int jumpFloor(int target) {
if(target==1){
return 1;

}else if(target==2){

    return 2;
}else {
    return jumpFloor(target-1)+jumpFloor(target-2);
}
}

}
复制代码
青蛙跳台阶是一个十分经典的问题，要想解决这道题，就必须要了解递归的思想，掌握递归的核心：大事化小 但是，递归的效率又不是很理想，所以我们有必要进行代码的优化 所以我们可以模仿求斐波那契数字一样，使用循环来进行优化

public class Solution {
if (n == 1 || n == 2) {

        return n;
    } else {
        int a = 1;
        int b = 2;
        int c = 0;
        for (int i = 3;  i <=n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

}

复制代码
这样子循环的效率就会高于递归的写法