题目是这样的:

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

P 015

How many such routes are there through a 20×20 grid?

这个题来自Project Euler第15题。翻译为中文的话,题意大致是:

从一个2x2的网络的左上角出发,只能向右或向下移动,到右下角一共有6种不同的走法。那么,对一个20x20的网络来说,有多少种不同的走法呢?

我们来绘制一个大一些的网格,并将它的横向记为X坐标,纵向记为Y坐标,每个交点依次编号,如下图:

Lattice paths 2

这样,我们都可以使用形如 (x, y) 这样的坐标来表示网格中的每一个交点了,比如下图中的黑点位置可以用坐标 (4, 3) 来表示。

Lattice paths 3

可以发现,如果从左上角即坐标 (0, 0) 处出发,只能向右或向下移动,到达接下来几个交点的走法类似下图所示:

Lattice paths 4

每个交点右下方的蓝色数字表示从左上角出发到达这个位置的不同走法,例如坐标 (2, 2) 右下角的数字是 6 ,即到达这个位置共有 6 种不同的走法。这也即原题中 2x2 的格子的不同走法。

观察这个网格,可以发现除了最上边及最左边的交点外,各个交点的走法等于它上方及左方交点走法的和。

Lattice paths 5

如上图所示,坐标 (4, 3) 处的走法共有 35 种,等于它上方的网格 (4, 2) 的走法(15种)加上它左方的网格 (3, 3) 的走法(20种)之和。

也就是说,如果用函数 r(x, y) 来表示到达坐标 (x, y) 的走法,我们可以总结出下面的公式:

Lattice paths 6

根据上面的公式,我们很容易编写出对应的代码来,以 Python 为例:

def r(x, y):

    if x == 0 and y == 0:
        p = 0
    elif x == 0 or y == 0:
        p = 1
    else:
        p = r(x - 1, y) + r(x, y - 1)

    return p

不过,需要注意的是,上面的代码用到了递归,当 x、y 的值变大时,递归的次数以指数级别上升,因此,要计算 r(20, 20) ,用这个方法效率是非常低的。我们可以再将程序改进一下,像下面这样:

def r(x, y):
    d = []
    for i in range(y + 1):
        t = [0] * (x + 1)
        d.append(t)

    for iy in range(y + 1):
        for ix in range(x + 1):
            if ix == 0 and iy == 0:
                v = 0
            elif ix == 0 or iy == 0:
                v = 1
            else:
                v = d[iy - 1][ix] + d[iy][ix - 1]
            d[iy][ix] = v

    return d[y][x]

这样便快很多了,很容易计算出,r(20, 20) 的值为 137846528820,也即对一个 20x20 的网格来说,从左上角走到右下角,一共有 137846528820 种不同的走法。

至此,这题便解答完成了,在Project Euler的论坛上还有很多种其他解法。另外,观察这个网格,每个交点处的值都是它上方及左方两个交点的值的和,这一点有点像斐波那契数列,不过形式上是二维的。