LeetCode爬楼梯算法仅n=43/45报错，求原因分析

你的代码核心思路是对的——通过统计使用i次2步的场景数（即从n-i个位置中选i个放2步，对应组合数C(n-i, i)），再累加所有可能的i值加上全走1步的情况。但在n=43、45时出错，问题出在浮点数精度丢失。

错误原因 #

当n增大到43、45时，阶乘的计算结果会远超双精度浮点数的精确表示范围（双精度浮点数仅能精确表示2^53以内的整数）。比如：

• 43! 的值是60415263063373835637355132068513997507264512000000000，这个数远大于2^53（约9e15），用浮点数存储时会被近似处理，丢失末尾的精确数位。
• 你在permutasyon函数中返回的是浮点数（faktoriyel(a)/faktoriyel(a-b)），后续除以faktoriyel(i)再转int时，因为浮点数已经是近似值，转整数会得到错误的结果，最终导致累加总和偏离正确值。

比如n=43，i=21时，组合数C(43-21,21)=C(22,21)=22，但用你的代码计算时，浮点数的近似误差会让结果偏离，进而影响最终总和。

修复方案 #

避免用浮点数计算组合数，直接用整数运算，或者利用Python内置的组合数函数math.comb（Python 3.10及以上版本支持），它会用整数运算保证精度。

方案1：使用内置math.comb

import math
class Solution:
    def climbStairs(self, n: int) -> int:
        total = 1  # 初始为全走1步的情况
        max_two_steps = n // 2
        for i in range(1, max_two_steps + 1):
            # 直接计算组合数C(n-i, i)，整数运算无精度丢失
            total += math.comb(n - i, i)
        return total

方案2：手动实现整数版组合数（兼容低Python版本）

class Solution:
    def climbStairs(self, n: int) -> int:
        def comb(a, b):
            if b > a - b:
                b = a - b  # 利用组合数性质C(a,b)=C(a,a-b)减少计算量
            result = 1
            for i in range(1, b+1):
                # 先乘后除保证每一步都是整数，避免精度损失
                result = result * (a - b + i) // i
            return result
        
        total = 1
        max_two_steps = n // 2
        for i in range(1, max_two_steps + 1):
            total += comb(n - i, i)
        return total

验证 #

修正后的代码在n=43时返回433494437，n=45时返回1134903170，均为正确的斐波那契数（爬楼梯问题本质对应斐波那契数列，f(n)=f(n-1)+f(n-2)，f(1)=1,f(2)=2）。

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