I see that if we call $f(x,y)$ the total number of way to get to cell $(x,y)$ from $(0,0)$ , then the number itself is the sum of the number of ways to get $(x-1,y)$ and $(x, y-1)$.
Then $f(x,y)=f(x-1,y)+f(x,y-1)$ with $f(0,i)=f(j,0)=1, 0<i<n+1$ and $0<j<m+1$.
If I solve the $n^{th}$ term of the recursive formula, the complexity would be $O(n^2)$. How to find the general formula to down it to $O(1)$?
On
This is equivalent to counting the number of sequences $D,R$ (down,right) containing $n$ "downs" and $m$ "rights".
Consider such a sequence, it is $m+n$ characters long and is uniquely determined by the position of the $m$ "rights" in it (because then you are forced to use "downs" in all other positions). The number of ways to position these $m$ "rights" in our $n+m$ "slots" is exactly ${m + n} \choose m$.
$\def\bl#1{{\color{blue}{#1}}}$ $\def\rd#1{{\color{red}{#1}}}$ $\def\gr#1{{\color{green}{#1}}}$ In general, it is $f(x,y) = {x+y\choose x}$, you can use the classical recurrence relation for the binomial $$f(x,y) = {x+y\choose x} = {x+(y-1)\choose x}+{(x-1)+y\choose x-1}=f(x,y-1)+f(x-1,y)$$ If we plot it we'll see pascal's triangle pretty clearly $$ \begin{array}{c|c|c|c|c} \bl 1 & \rd 1 & \gr 1 & \bl 1 & \rd 1\\\hline \rd 1 & \gr 2 & \bl 3 & \rd 4 & \gr 5\\\hline \gr 1 & \bl 3 & \rd 6 & \gr{10} & \bl{15}\\\hline \bl 1 & \rd 4 & \gr{10} & \bl{20}& \rd{35}\\\hline \rd 1 & \gr{5} & \bl{15} &\rd{35} &\gr{70} \end{array} $$