Problem 15

Problem 15

19 April 2002

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

我们令最右下角的点坐标为(0, 0), 令最左上角坐标为(i, j), 则(i, j)到(0, 0)的路线数为

(i-1, j)到(0, 0)和(i, j-1)到(0, 0)的路线数的和

a15 = {}

def getA15(i, j):
    if i == 0 or j == 0:
        a15[(i, j)] = 1
    else:
        if not a15.has_key((i,j)):
            a15[(i, j)] = getA15(i-1, j)+getA15(i, j-1)

    return a15[(i, j)]

def fun15():
    return getA15(20 ,20)

answer is 137846528820

还有一种更直接的方法，题目中只能向右和下移动，我们将向右移动看做0, 向下移动看做1, 则一共需要向右移动20步和向下移动20步，相当于20个1和20个0的组合

一共(40!)/((20!)*(20!)) = 137846528820