青蛙跳台阶问题

image-20220404162919833

文字表述

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

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

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

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;
        }
}

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