Given a N*N chess board, a robot starts from the left-up corner and ends at right-down corner. It can only move one cell per time and the direction mu

Given a N*N chess board, a robot starts from the left-up corner and ends at right-down corner. It can only move one cell per time and the direction must be right or down

Give the algorithm that count all possible paths.
For an NxN square it takes (2N - 2) steps to move from the upper left corner to bottom right corner. Of these steps, half must be right and half must be down (N - 1 in each direction). Knowing this, we can look at it as a string permutation or how many ways can you write "RRRDDD", etc. (this would be for N = 4, "RRDD" for N = 3 and so on). Now we just have to count the number of permutations for this string which in terms of N will be (2N - 2)!/((N - 1)!(N - 1)!).

int foo(int n, int i,int j)//O(2^n)
{
if(i==n&&j==n) return 1;
if(i>n||j>n) return 0;
return foo(n,i+1,j)+foo(n,i,j+1);
}


int arr[n][n]={0};
int foo(int n, int i, int j)//O(n^2)
{

if(i==n&&j==n) return 1;
if(i>n||j>n) return 0;
if(arr[i+1][j]&&arr[i][j+1])
arr[i][j]=arr[i+1][j]+arr[i][j+1];
else if(arr[i+1][j])
arr[i][j]=arr[i+1][j]+foo(n,i,j+1);
else if(arr[i][j+1])
arr[i][j]=foo(n,i+1,j)+arr[i][j+1];
else arr[i][j]=foo(n,i+1,j)+foo(n,i,j+1);
return arr[i][j];
}