Unique Paths in a grid

A robot is located at the top-left corner of a row x col grid The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?

Below is an example of 4x4 grid. Here from moving top-left to bottom right corner, we will have 20 unique paths.

1 1 1 1
1 2 3 4
1 3 6 10
1 4 10 20

Strategy:
Since we know that one can only move either down or right at any point in time so one can reach to cell (i,j) only from 2 possible locations:

• One step right from cell (i-1,j)
• One step down from cell (i,j-1)

So unique no of paths to reach any cell (i,j) will be equal to sum of unique no of paths to reach any cell (i-1,j) and unique no of paths to reach any cell (i,j-1). We can convert the same formula into code using 2 approaches:

• Recursion / Backtracking
• Dynamic programming.

In backtracking we will calculate the no of paths for same locations again and again but in Dynamic programming (DP) approach, we can use memoization and will get rid of calculating same locations again and again. For DP soluton just initialize a 2D array(sat paths) of size m x n with all elements as 1. And then apply the formula:

Paths[i][j] = paths[i][j-1] + paths[i-1][j]

After calculating the entire 2D array, just return paths[m][n]
Complexity: Since we are traversing each element just once, this solution has linear time complexity


Code:
int uniquePaths(int row, int col)
{ 
       int matrix[row][col];
        int i=0,j=0;
       // set the initial conditions
       for(i=0;i < row;i++)
          matrix[i][col-1]=1;

       for(j=0;j < col;j++)
          matrix[row-1][j]=1;
       // there is no path when we have reached
       //  the destination
       matrix[i][j]=0;
       
       // starting from the diagonal position and
       // moving upwards and leftwards
       for (i = row-2; i >= 0; i--)
       {
         for (int j = col-2; j >= 0; j--)
         {
              matrix[i][j] = matrix[i+1][j] + matrix[i][j+1];
         }
       }
       return matrix[0][0];
}
Alternatively,

 int no_of_paths(int width, int height)
 {
    //Creating paths
    int** paths = new int*[height];
    for(int i = 0; i < height; ++i)
        paths[i] = new int[width];
   
    int i,j;
   
    //Initializing paths
    for (i=0 ;i< width; i++)
    {
        for (j=0; j< height; j++)
            paths[i][j] = 1;
    }

    //Calculating paths  
    for (i=1 ;i< width; i++)
    {
        for (j=1; j< height; j++)
        {
            paths[i][j] = paths[i-1][j] + paths[i][j-1];
        }
    }
    //just for printing/debugging purpose  
    for (i=0 ;i< width; i++)
    {
        for (j=0; j< height; j++)
        {
            cout << paths[i][j] << " ";
        }
        cout << endl;
    }
       
    int res = paths[width-1][height-1];

    //Deleting paths  
    for(int i = 0; i < height; ++i) {
        delete [] paths[i];
    }
    delete [] paths;
   
    return res;
 }

Using 1d Array:

Instead of using a 2d array, We can have 1d Array with length as width

int no_of_paths(int width, int height)

{ 

 int i,j;

 int* no = new int[width];

 

 for (i=0 ;i< width; i++)

 {

  no[i] = 1;

  cout << "1 "; //just for printing/debugging purpose

 }

 cout << endl;     //just for printing/debugging purpose

 

 for (i=1 ;i< height; i++)

 {

  cout << no[0] << " ";     //just for printing/debugging purpose

  for (j=1; j< width; j++)

  {

   no[j] = no[j]+no[j-1];

   cout << no[j] << " "; //just for printing/debugging purpose

  }

  cout << endl;             //just for printing/debugging purpose

 }

 int res = no[width-1];

 

 delete [] no; 

 return res;

}