Project Euler problem involving optimization

This is about my try at a moderate level programming problem from Project Euler, problem # 15.
With usual approach (and attitude), I thought I should be done in 15 minutes on this one, but stretched me for six times that estimate.
Problem is about finding the number of routes through a n*n grid, starting from top-left and ending at bottom-right (for n=20).

My sequence of attempts -
1/ Simplest recursive function that traversed right and down and counted routes on reaching destination. Too bad, it took unacceptably long for n=20 case. In retrospect, I should have avoided coding this approach, knowing the size of inputs.
2/ Making a recurrence relation, with the hope that I would not even need a program to calculate this. That is, if the problem of size N can be expressed in terms of problems of (size < N) and the if I could get a closed form, simple calculation would have done it.
I got this -
For a grid size (m*n),
T(m, n) = T(m-1, n)+T(m, n-1) ..... m <> n
2*T(m-1, n) ..............m==n

For the case when m==n, we have utilized the symmetry : T(m-1, n)=T(m, n-1).

Bringing this recurrence to a closed form is beyond my technical means today, so I modified the code to follow this recurrence and calculate. This too failed since the size n=20 was overwhelming my 64-bit dual core server even then.

3/ After almost giving up after some frustrating debugging and some old fashioned pen-paper workout of the recursion, I wanted to create a cache of T(m, n) values that were getting calculated. Certainly, many values were being repeatedly calculated in various "branches" of the recursion. In this case, the cache needed was no more bigger than n*n=400. So now the code only calculated a T(m, n) if it was being caclulated for the first time and re-used that.
Now the code was terminating in a flash even for large input sizes, but throwing wrong answers.
4/ The last mistake was about the return data-type of the function, that needs to be kept in min for almost all Euler problems. It was a silly 'int'. C++ did not warn of truncation, never mind what the compiler option was.

So I have a few things to take home today, caching at appropriate places being the most important of them.