计算N阶网格中路线组合的数量

Question

我需要写一段代码，来计算在一个 N x N 的网格中，从左上角到右下角的不同走法组合的数量。注意，我只能向下走或者向右走！

简单来说，如果我们给每个点编号，从 1 到 (N+1)²，那么我想知道从 1 到 (N+1)² 有多少种不同的组合。不过我只能加 1 或者加 N+1。

举个例子：2x2 的网格：

1 -- 2 -- 3
|    |    |
4 -- 5 -- 6
|    |    |
7 -- 8 -- 9

而这些组合会是：

[1-2-3-6-9]
[1-2-5-6-9]
[1-2-5-8-9]
[1-4-5-6-9]
[1-4-5-8-9]
[1-4-7-8-9]

那么，我该如何写这段代码呢？任何帮助都非常感谢！
提前谢谢你！

Answer 1

哦，我明白你在尝试解决欧拉项目的问题了？关键是要自己搞明白，并在这个过程中学到新东西！如果你作弊，只是在骗自己罢了。唉，没办法。

无论如何，想象一下一个有 m 行 n 列的网格（我们不需要假设这个网格是正方形的）。从左上角开始，编号从零开始，i 行 j 列的交点/节点用 N_(i,j) 表示。

所以，左上角的节点是 N_(0,0)，左下角是 N_(m,0)，右下角是 N_(m,n)。很明显，从 N_(0,0) 到网格的最右边或最上边的任何节点，路径只有 1 条（因为我们只能向下或向右走）。

现在，考虑一下到 N_(1,1) 有多少条路径。我们必须先经过 N_(0,1) 或 N_(1,0)。这样到 N_(1,1) 只有两条路径。我们可以继续这个过程。为了确定到任何节点 N_(i,j) 的总路径数，我们只需要把到 N_(i,j−1) 和 N_(i−1,j) 的路径数加起来。这个过程可以通过下面的图示来理解，每个新数字代表到一个节点的路径数。

如果我们用 Python 编写这个代码，结果是：

def route_num(cube_size):
    L = [1] * cube_size
    for i in range(cube_size):
        for j in range(i):
            L[j] = L[j]+L[j-1]
        L[i] = 2 * L[i - 1]
    return L[cube_size - 1]

运行 print route_num(20) 会给我们 137846528820 的结果。

来源：http://code.jasonbhill.com/