京公网安备11010502063487号机器人在 m × n 网格的左上角，每次只能向右或向下走一格，问走到右下角一共有多少条不同的路径。这是动态规划的入门题：走到 (i, j) 的路径数，等于走到它上面那一格的路径数加上走到它左边那一格的路径数；第一行和第一列每格只有一条路。这道题还有一个数学解：一共要走 m + n - 2 步，其中 m - 1 步向下，路径数就是组合数 C(m+n-2, m-1)。本文用真实数据展示不带记忆化的递归会有多慢，验证动态规划和组合数答案一致，实测两者的耗时，给出五种语言的实现，并把填表的过程做成分步演示。
完整题目见官方页面（链接在文末）。答案保证不超过 20 亿，所以 Java、C++ 里用 32 位整数存放就够了。基准解用组合数：comb(m + n - 2, m - 1)，与逐格累加是完全不同的思路。一共 13 组用例，覆盖：官方示例、只有一行或一列（答案是 1）、方阵、以及答案接近 20 亿的大网格（例如 17×17 是 601080390）：
输入 [3,7] 输出 28 输入 [3,2] 输出 3 输入 [7,3] 输出 28 输入 [1,1] 输出 1 输入 [1,10] 输出 1 输入 [10,1] 输出 1
最直接的递归写法是：paths(m, n) = paths(m-1, n) + paths(m, n-1)，到第一行或第一列返回 1。它的问题是同一个格子会被反复计算。下面是真实统计的调用次数：
朴素递归（不做记忆化）的调用次数与耗时： m=n= 5: 结果 70，递归调用 139 次， 0.01 ms；动态规划需要 25 个格子 m=n= 8: 结果 3432，递归调用 6863 次， 0.43 ms；动态规划需要 64 个格子 m=n=10: 结果 48620，递归调用 97239 次， 6.24 ms；动态规划需要 100 个格子 m=n=12: 结果 705432，递归调用 1410863 次， 89.44 ms；动态规划需要 144 个格子 m=n=14: 结果 10400600，递归调用 20801199 次， 1321.00 ms；动态规划需要 196 个格子
调用次数几乎正好是路径数的 2 倍减 1（n = 5 时 139 = 2 × 70 - 1，n = 8 时 6863 = 2 × 3432 - 1，n = 10 时 97239 = 2 × 48620 - 1）：递归树每个叶子对应一条路径，每条路径都要单独走一遍。n = 14 时结果是 10400600，递归调用超过 2000 万次，耗时 1321ms；而动态规划只需要 14 × 14 = 196 个格子。
用一维数组 dp，dp[j] 表示走到当前行第 j 列的路径数，初始时（第一行）每个格子都是 1。对第 1 行到第 m-1 行，对每一列 j 从 1 开始：dp[j] += dp[j - 1]，这里 dp[j] 原本存的是上一行同一列的值（从上面来），dp[j - 1] 已经是当前行左边一格的值（从左边来）。最后返回 dp[n - 1]。空间只需要一行。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(m, n): dp = [1] * n # dp[j]：走到当前行第 j 列的路径数；第一行每格都只有 1 条路（一直向右） for _ in range(1, m): for j in range(1, n): dp[j] += dp[j - 1] # 到 (i, j) = 从上面来（旧的 dp[j]）+ 从左边来（dp[j-1]） return dp[n - 1]
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [3,7] → 28 [3,2] → 3 [7,3] → 28 [1,1] → 1 [1,10] → 1 [10,1] → 1
Java · 解法代码class Solution { public int uniquePaths(int m, int n) { int[] dp = new int[n]; // dp[j]：走到当前行第 j 列的路径数 Arrays.fill(dp, 1); // 第一行每格都只有 1 条路（一直向右） for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] += dp[j - 1]; // 到 (i, j) = 从上面来（旧的 dp[j]）+ 从左边来（dp[j-1]） } } return dp[n - 1]; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [3,7] → 28 [3,2] → 3 [7,3] → 28 [1,1] → 1 [1,10] → 1 [10,1] → 1
Go · 解法代码func uniquePaths(m int, n int) int { dp := make([]int, n) // dp[j]：走到当前行第 j 列的路径数 for j := range dp { dp[j] = 1 // 第一行每格都只有 1 条路（一直向右） } for i := 1; i < m; i++ { for j := 1; j < n; j++ { dp[j] += dp[j-1] // 到 (i, j) = 从上面来（旧的 dp[j]）+ 从左边来（dp[j-1]） } } return dp[n-1] }
$ go build -o bin . && ./bin < cases.jsonl [3,7] → 28 [3,2] → 3 [7,3] → 28 [1,1] → 1 [1,10] → 1 [10,1] → 1
JavaScript · 解法代码function uniquePaths(m, n) { const dp = new Array(n).fill(1); // dp[j]：走到当前行第 j 列的路径数；第一行每格都只有 1 条路 for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[j] += dp[j - 1]; // 到 (i, j) = 从上面来（旧的 dp[j]）+ 从左边来（dp[j-1]） } } return dp[n - 1]; }
$ node run.js < cases.jsonl [3,7] → 28 [3,2] → 3 [7,3] → 28 [1,1] → 1 [1,10] → 1 [10,1] → 1
C++ · 解法代码#include <vector> using namespace std; class Solution { public: int uniquePaths(int m, int n) { vector<int> dp(n, 1); // dp[j]：走到当前行第 j 列的路径数；第一行每格都只有 1 条路 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] += dp[j - 1]; // 到 (i, j) = 从上面来（旧的 dp[j]）+ 从左边来（dp[j-1]） } } return dp[n - 1]; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [3,7] → 28 [3,2] → 3 [7,3] → 28 [1,1] → 1 [1,10] → 1 [10,1] → 1
共 13 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 13/13 Java 通过 13/13 Go 通过 13/13 JavaScript 通过 13/13 C++ 通过 13/13
m = n 分别为 10、100、300、1000，每个规模取三次中最快的一次（Python 的整数不会溢出，所以这里的路径数会非常大）：
m = n | 暴力解 | 本文解法
10 | 0.000 ms | 0.003 ms
100 | 0.005 ms | 0.307 ms
300 | 0.020 ms | 3.622 ms
1000 | 0.117 ms | 59.818 ms动态规划是 O(mn)：从 100 到 300（3 倍）耗时增长约 11.8 倍，从 300 到 1000（3.3 倍）增长约 16.5 倍，符合平方（略高，因为路径数变成了巨大的整数，加法本身也变慢了）。组合数是 C 实现的一次计算，1000 × 1000 只要 0.117ms，而动态规划要 59.8ms，约 500 倍。这个差别来自 Python 解释器与 C 的差距，也来自算法：组合数不需要逐格累加。但组合数的计算在其他语言里会遇到整数溢出，需要小心（先乘后除的中间结果很大），所以本文的五种语言实现都用了动态规划。
Python 版本另外和组合数做了随机对拍，m、n 各取 1 到 15：
随机对拍 2000 组（m、n 各取 1 到 15 的随机值），solve 与 brute 的结果全部一致。
另外四种语言只在上面 13 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用 3 行 7 列的网格（官方示例）。第一行和第一列全是 1；然后逐格填：每个格子等于上面那格加左边那格。最后右下角的值 28 就是答案。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。