# Statement

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

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

# Solution

Here we have to apply dynamic programming to solve it. That means solve the problem in smaller steps.

For this situation you have to imagine a matrix of points(each corner) as we are not able to backtrack,

all the point in the top row are only accessible through one route, the one that goes straight. The same

happens with the column on the left.

For the interior points, the number of routes is determined by the sum of the number of routes we have

until the corner above the point and the one on its left.

For a 2×2 grid we would build a matrix of 3×3(remember it's the corners we need) and initialize it this way:

1, 1, 1

1, 0, 0

1, 0, 0

and then we start processing rows from top to bottom:

1, 1, 1

1, 2, 3

1, 0, 0

1, 1, 1

1, 2, 3

1, 3, 6

Now we just have to check the bottom right cell for the content and we have the answer.

if __name__ == '__main__': #Building the matrix sqre = [[]] for i in range(21): sqre[0].append(1) for i in range(1,21): row = [1] for i in range(1,21): row.append(0) sqre.append(row) #Processing the routes for i in range(1,21): for j in range(1, 21): sqre[i][j] = sqre[i-1][j] + sqre[i][j-1] print("The result is:", sqre[20][20])

The Python file is available for download here.