能帮我分析一下两个算法吗。

Question

第一种用的时间很长，在输入50左右的数据时，两种方法的答案不同，但50之前的数据是一样的，是怎么回事呢，谢谢！！

原题：学完青蛙跳楼梯之后，小明突发奇想，如果我先迈左脚，而且要求最后一次也是踏左脚，每步可以跨1-2阶，那么1个9阶的楼梯，我会有多少种方法上楼呢？他编程实现了之后并实际测试了一下，9阶一共有27种上楼的方法。那么50阶、90阶呢？

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();/////////输入阶数
        System.out.print(fun(n+1,false));
    }
    public static int fun(int jie,boolean leftfoot) {///////////jie是当前站的jie（n+1）
        if(jie == 3) {
            return 1;
        }
        if(jie == 4) {
            if(leftfoot) {
                return 2;
            }else {
                return 1;
            }
        }
        return fun(jie-1,!leftfoot)+fun(jie-2,!leftfoot);

    }
}

import java.util.Scanner;

public class Main {
    static long[] left = new long[93];
    static long[] right = new long[93];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); 
        //初始化    left[1]代表1阶的时候左脚到达终点的方法数  right[2]代表2阶的时候右脚到达终点的方法数
        left[1] = left[2] = right[2] = 1;
        for (int i = 3; i <= 92; i++) {
            left[i] = right[i - 1] + right[i - 2]; //左脚到达终点   那么说明在i-1阶 或者 i-2阶 的时候踏上去的是 右脚
            right[i] = left[i - 1] + left[i - 2];
        }
        System.out.println(left[n]);
    }
}

Answer 1

https://zhidao.baidu.com/question/564251521.html