Project Euler problem 15 : code and explanation

The problem is simply stated as -

Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Note, we can not move up, or left at any point.
For input 2, there are 6 ways, as shown-

Solution 1- There is a combinatorics solution, which reduces the problem to a simple expression, in terms of 'N', but I solved it using Dynamic Programming, which is solution 2. If you want the expression, just ask :)

Solution 2 - There is a common problem in programming, where we need to find the sum of elements in a NxN matrix, moving from top left to bottom right, in same fashion. So I just use the strategy, but instead of summing the elements, I counted the number of paths. Also for a input N, the DP solution of mine needs a matrix of size (N+1)x(N+1). Try visualizing the above image imposed on a 3x3 matrix.

Python code-

#Problem 15

import numpy

table = numpy.zeros((21, 21), dtype=numpy.int64)

def rec(r, c):
    if table[r, c] != 0:
        return table[r, c]
    if r == 0 and c == 0:
        return 1
    rsum = 0
    csum = 0
    if r != 0:
        rsum = rec(r-1, c)
    if c != 0:
        csum = rec(r, c-1)
    table[r, c] = rsum + csum
    return rsum + csum

if __name__ == "__main__":
    n = int(raw_input("Enter n : "))
    print rec(n, n)

If I remove the memoization, the input number '20' will take forever to come with solution.