二维数组左上角到右下角路径数的解析解法疑问（《编程面试元素》16.3）

我明白你为啥会对这个解析解法犯嘀咕——毕竟动态规划是一步步递推出来的，看得见摸得着，而组合数解法一下子跳到公式，感觉有点“凭空出现”的意思。我来给你拆解清楚这个逻辑：

首先，咱们先把问题的本质抓准：从(0,0)走到(n-1,m-1)，只能向右（水平）或者向下（垂直）走对吧？那不管你走哪条路径，有个事实是绝对不变的：

• 你需要向下走n-1次：因为从第0行到第n-1行，一共要跨n-1行；
• 你需要向右走m-1次：从第0列到第m-1列，一共要跨m-1列；
• 总共走的步数就是 (n-1)+(m-1) = n+m-2 步。

现在问题就转化成了：在这n+m-2步里，我们要选择哪几步是向下走（剩下的自然就是向右走），或者反过来选择哪几步是向右走——这完全就是组合数要解决的问题啊！

组合数C(a, b)的定义就是：从a个不同元素中选出b个元素的所有可能方式数。对应到这里：

• a就是总步数 n+m-2；
• b就是向下走的步数 n-1（或者向右走的步数m-1，因为C(a,b)=C(a,a-b)，结果是一样的）。

所以路径数就是C(n+m-2, n-1)，展开就是阶乘形式：(n+m-2)!/((n-1)!(m-1)!)。

举个简单例子验证下：比如2行2列的网格（n=2，m=2），路径数应该是2条：右→下，或者下→右。代入公式：C(2+2-2,2-1)=C(2,1)=2，完全对得上。再比如3行3列的网格，路径数是6条，公式算出来C(3+3-2,3-1)=C(4,2)=6，也没错。

要是你还是觉得抽象，就把每一步看成一个位置，比如总共有4个位置（3行3列的情况），选2个位置放“向下”，剩下的放“向右”，每一种选法对应一条唯一的路径，这样是不是就好理解多了？

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