两种n阶楼梯路径计数方法的逻辑差异及异常问题排查

计算从第1阶楼梯出发，每次走1阶或2阶时到达第n阶楼梯的路径数，以下第一种方法运行正常，但第二种方法在n较大时无法得到正确结果。例如输入n=87时，第二种方法输出-334512466，期望输出为665487541。

方法01（运行正常） #

//---01--------
int mod = (int)1e9+7;
int prev1 = 1;
int prev2 = 1;
for(int i = 2; i <= n; i++){
    prev2 = (prev2 + prev1) % mod;
    prev1 = prev2 - prev1;
}
return prev2;

方法02（n较大时出错） #

//---02--------
int mod = (int)1e9+7;
int prev1 = 1;
int prev2 = 1;
for(int i = 2; i <= n; i++){
    int curr = (prev2 + prev1) % mod;
    prev1 = prev2;
    prev2 = curr;
}
return prev2;

问题原因 #

第二种方法的核心问题是int类型溢出：

• Java中int是32位有符号整数，最大值为2147483647，而模值1e9+7（即1000000007）接近这个上限。当n增大时，prev2 + prev1的结果可能超过int的最大值，触发溢出后会变成负数。
• 负数对1e9+7取模后仍为负数，后续循环中基于负数计算的结果会持续错误，最终得到负数输出。

修复方案 #

将求和操作改用long类型计算，避免溢出后再转成int赋值：

//---修复后的方法02--------
int mod = (int)1e9+7;
int prev1 = 1;
int prev2 = 1;
for(int i = 2; i <= n; i++){
    long curr = ((long)prev2 + prev1) % mod;
    prev1 = prev2;
    prev2 = (int)curr;
}
return prev2;

内容的提问来源于stack exchange，提问作者Susanta Adak