How do I add memoization to this problem? Problem
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?

Solution
Here is my solution

    def step(i,j):
    if(i==20 or j==20):
        return 1
    return step(i+1,j)+step(i,j+1)
print step(0,0)


But this takes too long to run, how can this be optimized?
Finally my memoization technique worked and the result appears in less than a sec

    cache = []
for i in range(20):
    cache.append([])
    for j in range(20):
        cache[i].append(0)

def step(i,j):
    if(i==2 or j==2):
        return 1
    if(cache[i][j]&gt;0):
        return cache[i][j]
    cache[i][j] = step(i+1,j)+step(i,j+1)
    return cache[i][j]
print step(0,0)


Another optimization I have added (since step(i,j) is same as step(j,i)) 

    cache = []
for i in range(20):
    cache.append([])
    for j in range(20):
        cache[i].append(0)

def step(i,j):
    if(i==20 or j==20):
        return 1
    if(cache[i][j]&gt;0):
        return cache[i][j]
    cache[i][j] = step(i+1,j)+step(i,j+1)
    cache[j][i] = cache[i][j]
    return cache[i][j]
print step(0,0)