我工资6000，新来的8000，知道后和老板大吵一架，辞职去了别的公司月薪 1w。但昨天老板给我打电话，让我回去解决一个问题。。

在写代码的过程中，我们总是会遇到一些看似简单，但细想之下却隐藏着坑的算法题。今天的这个问题是：统计所有可行路径。

举个例子，假设你站在一个二维网格的左上角，你只能向右或向下移动，要走到右下角，总共有多少条不同的路径？

经典的“走格子”问题，这在面试里可算是老朋友了。乍一看，可能会有人想：“这不就是暴力搜索嘛，直接递归就能搞定！”

但凡是经历过面试折磨的同学都知道，这题如果用暴力递归来解，一定会超时。面试官不会明说，但他心里已经开始疯狂打 ❌ 了。

正确的解法，得从 动态规划（Dynamic Programming） 和 组合数学（Combinatorics） 这两个方向来考虑。

1. 经典动态规划解法

如果你定义 dp[i][j] 为从 (0,0) 走到 (i,j) 的路径数，那么显然有个递推关系：

换句话说，能走到 (i, j)，要么是从 (i-1, j) 走过来的，要么是从 (i, j-1) 走过来的，所以它们的路径数加起来就是当前格子的路径数。

Python 实现如下：

defunique_paths(m, n):
    dp = [[1] * n for _ in range(m)]  # 初始化所有格子路径数为 1

for i in range(1, m):  # 从 1 开始，因为 (0,0) 是起点
for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

return dp[m-1][n-1]

print(unique_paths(3, 7))  # 输出 28

这段代码的时间复杂度是 **O(m × n)**，空间复杂度也是 **O(m × n)**，但我们可以优化空间，把 dp 数组压缩成一维的。因为计算 dp[i][j] 时，其实只依赖当前行和上一行的值，所以只需要一行滚动数组就能搞定：

defunique_paths_optimized(m, n):
    dp = [1] * n  # 只需要一维数组

for i in range(1, m):  
for j in range(1, n):
            dp[j] += dp[j-1]  # 当前位置等于左边+上面的值

return dp[-1]

print(unique_paths_optimized(3, 7))  # 还是 28

2. 组合数学解法

如果你仔细观察，其实从 (0,0) 走到 (m-1,n-1)，无非就是往右 n-1 步，往下 m-1 步，总共需要 m+n-2 步，其中 n-1 步是向右走的，其余是向下走的。

问题就变成了：从 m+n-2 步里选 n-1 步向右走，一共有多少种方案？

这就变成了组合数的计算，即：

用 Python 实现如下：

import math

defunique_paths_math(m, n):
return math.comb(m+n-2, n-1)

print(unique_paths_math(3, 7))  # 依旧是 28

这个解法时间复杂度是 **O(1)**，超级快，适合 m 和 n 很大的时候。

所以，面试的时候，先写动态规划，面试官会觉得你很稳重；然后再甩出组合数学的解法，面试官就该对你点头微笑了 。

当然，这个题的变种也不少，比如加上障碍物，比如问最短路径权重之类的，都是可以拓展的点。面试嘛，考的就是套路和变通能力，掌握了这些，就能在关键时刻用对方法，拿下 offer！