欧拉计划(python) problem 15

Lattice paths

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.

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

python code :

dict={}
def func(i,j):
    rest=dict.get(str(i)+‘_‘+str(j))
    if rest!=None:
        return rest
    else:
        if i==0 and j==0:
            return 0
        if i==0 or j==0:
            return 1
        temp=func(i-1,j)+func(i,j-1)
        dict[str(i)+‘_‘+str(j)]=temp
        return temp

result=func(20,20)
print(result)

time : <1s

欧拉计划(python) problem 15

原文：http://blog.csdn.net/zhangzhengyi03539/article/details/43193087