015. 格子路径(lattice paths)

在一个2×2的栅格中,从左上角出来,只能向右或向下移动,总共有6条路径可以到达栅格的右下角:

IMG

求在一个20×20的栅格中,有多少条移动路径?

分析:此题至少有两种解法,一种是应用排列组合知识的方法,另一种是动态规划的方法。下面先看排列组合的方法。如题目所述,要从(0,0)到达(2,2)我们需要向下走两步,向右走两步,总共需要走四步,这四步中有两步是向右走的,两步是向下走的。因此问题变成从四步任选出两步向右走,剩下的两步则向下走。比如你可以第一步和第二步向右走,剩下两步向下走,也就是图一;或者也可以第一步和第三步向右走,第二和第四步向下走,也就是图二。因此,这只是一个简单的组合问题,即从四步中任选出两步向右走共有多少种选法,显然有\(C(4,2)=6\)种选法。一般地,要从(0,0)走到(n,n)需要向下走n步,向右走n步,总共走2n步,因此总的可选路径共有\(C(2n,n)\)条,则题目要求答案即为\(C(40,20)\)。这个可以用组合数公式轻易计算出来。

第二种是动态规划的方法。首先考虑子问题,如在题目中一步可以到达(2,2)点的点只有两个,分别是(2,1)和(1,2),则到达(2,2)点的路径数也就是到达(2,1)点的路径数加上到达(1,2)点的路径数,而到达(2,1)点的路径数等于到达(1,1)点的路径数加上到达(2,0)点的路径数。因此一般地,到达点(x,y)的路径数等于到达(x-1,y)的路径数加上到达(x,y-1)的路径数,显然可以用自下而下的动态规划轻易解决。此题的边界条件是,一旦x或者y的坐标为零,则到达该点的路径只有一条。因此,我们将该动态规划问题的状态转移方程表述如下:

$$ p(x,y)= \begin{cases} p(x-1,y)+p(x,y-1) & x,y>0\\ 1 & x=0 \ or\ y=0 \end{cases} $$

利用该状态转移方程我们可以轻易写出自下而上动态规划的实现,我们可以利用python中的lru_cache装饰器实现自下而下动态规划的记忆化,提高代码执行的效率。两种方法的代码如下:

# approach 1, time cost = 140 ns ± 11.8 ns

from functools import lru_cache

@lru_cache(maxsize=128)
def path(x,y):
    if x == 0 or y == 0:
        return 1
    else:
        return path(x-1,y) + path(x,y-1)

# approach 2, time cost = 1.76 µs ± 83.9 ns

from math import factorial as fac

def comb_num(n,k):
    num = fac(n)//(fac(n-k)*fac(k))
    return num

def main(n,k):
    return comb_num(n+k,k)