第三十九级台阶问题，递归，斐波那契

Question

问题遇到的现象和发生背景

刷题时遇到这个题目，我想了想，这就是斐波那契的变种，于是就自己写了，然后就出问题了

问题相关代码，请勿粘贴截图

public class 第三十九级台阶 {
static int count;
public static void main(String[] args) {
int n=39;
int sum=fib(n);
System.out.println(sum);
}

public static int fib(int n){
    if(n==2) return 1;
    if(n==3) return 2;
    if(n==4) return 2;
    if(n==5) return 4;
    return fib(n-2)+fib(n-3)+fib(n-4);
}

}

运行结果及报错内容

我的答案是7位数，1587660，然而答案是一个八位数51167078

我的解答思路和尝试过的方法

既然要求是偶数步了，那我不妨把左右步合并为一个大步，每走两步为一个大步。
走一次大步，可能出现走两层、三层、四层的情况。于是递归的是三个相加

我想要达到的结果

跟答案一样是八位数

Answer 1

其他方法，网上也是有的。
只是我想把这个思路弄会，知道这种方法在逻辑上哪里错了。
不然以后再遇到类似的问题，或者算法考试的时候遇到了，总不能现场“求助诸贤”吧