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