JavaScript实现Hackerrank格子路径问题遇超时与计算错误求助

问题背景 #

我在用JavaScript解决Hackerrank上的Project Euler格子路径问题时，最初用递归方法在Project Euler上能通过，但放到Hackerrank后所有隐藏测试用例都超时：

const latticePathsRecursive = (m, n = m) => {
    if (m < 0 || n < 0) return 0;
    if (m === 0 && n === 0) return 1;
    return (latticePathsRecursive(m - 1, n) + latticePathsRecursive(m, n - 1));
}

改用组合数学解法后，仅通过样例和1个隐藏用例，其余均答案错误：

const latticePathsCombinatorial = (a, b) => {
   const factorial = (number) => {
      if (number === 1 || number === 0) {
         return 1;
      } else {
         return number * factorial(number - 1);
      }
   }

   let n = a + b,
   k = a;

   // 'n choose k' = n! / (k! * (n - k)!)
   return factorial(n) / (factorial(k) * factorial(n - k));
}

错误原因 #

问题出在JavaScript的Number类型精度限制：

• Number的安全整数上限是2^53 - 1，当a和b较大时，n = a + b的阶乘会远超这个值，导致Number无法精确存储大数，计算时出现精度丢失，最终组合数结果错误。

修正方案 #

方案1：用BigInt处理大数计算 #

将所有数值转换为BigInt类型，它支持任意大的整数运算，不会出现精度丢失：

const latticePathsCombinatorial = (a, b) => {
   const factorial = (number) => {
      let result = 1n;
      for (let i = 2n; i <= number; i++) {
         result *= i;
      }
      return result;
   }

   const n = BigInt(a + b);
   const k = BigInt(a);

   // 'n choose k' = n! / (k! * (n - k)!)
   return factorial(n) / (factorial(k) * factorial(n - k));
}

方案2：优化组合数计算（避免大数阶乘） #

通过逐步相乘约分的方式计算组合数，减少中间值的大小，同时用BigInt保证精度：

const latticePathsCombinatorial = (a, b) => {
    let n = a + b;
    let k = Math.min(a, b); // 取较小的k减少循环次数
    let result = 1n;
    for (let i = 1n; i <= BigInt(k); i++) {
        // 每一步都是整数除法，不会有精度问题
        result = result * BigInt(n - k + i) / i;
    }
    return result;
}

这种方法的优势是：组合数C(n,k) = C(n, n-k)，取较小的k能减少循环次数；逐步计算时每次都做约分，避免了直接计算超大数阶乘的问题，效率和精度都更高。

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