LeetCode 62. 不同路径 — JavaScript 实现题目思路机器人每次只能向右或向下走。到(i, j)的路径数 到(i-1, j)的路径数 到(i, j-1)的路径数。解法一DP一维优化/** * param {number} m * param {number} n * return {number} */varuniquePathsfunction(m,n){// dp[j] 表示当前行第 j 列的路径数constdpnewArray(n).fill(1);for(leti1;im;i){for(letj1;jn;j){dp[j]dp[j-1];}}returndp[n-1];};复杂度时间 O(m×n)空间 O(n)。解法二组合数学一共要走(m-1)次向下 (n-1)次向右共mn-2步选其中m-1步向下或n-1步向右即可varuniquePathsfunction(m,n){// 计算 C(mn-2, m-1)注意先除后乘避免大数溢出letresult1;constkMath.min(m-1,n-1);for(leti1;ik;i){resultresult*(mn-1-i)/i;}returnresult;};复杂度时间 O(min(m, n))空间 O(1)。示例验证以m 3, n 7为例答案 28解法一第一行dp [1,1,1,1,1,1,1]逐行累加后最终dp[6] 28✅解法二C(8, 2) 8×7/2 28✅说明JS 中普通 Number 可安全表示到 2^53LeetCode 62 的数据范围m, n ≤ 100C(198, 99)约 9×10^56实际上会超出安全整数范围。但题目约束下返回结果在评测机的浮点比较中是可接受的如需严格精确可用BigInt实现组合数varuniquePathsfunction(m,n){constkMath.min(m-1,n-1);letnum1n,den1n;for(leti1n;iBigInt(k);i){num*BigInt(mn-2)-i1n;den*i;}returnNumber(num/den);};推荐使用解法一一维DP最稳妥且无精度问题。