Unique Paths in 2D grid

Problem :

There is an m x n grid. One can only move either down or right at any point in time. One is trying to reach the bottom-right corner of the grid.

How many possible unique paths are there?
(project euler problem 15)
The similar question has been asked in Cracking the coding interview: Here we have to count the unique paths, but there we have to find the unique paths.



Example
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

Solution 

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 3 approaches:

• Recursion / Backtracking
• Dynamic programming.
• Treating it as counting problem of Permutation and combination

Method 1 - backtracking
The most direct way is to write code that traverses each possible path, which can be done using backtracking. When you reach row=m and col=n, you know you’ve reached the bottom-right corner, and there is one additional unique path to it. However, when you reach row>m or col>n, then it’s an invalid path and you should stop traversing. For any grid at row=r and col=c, you have two choices: Traverse to the right or traverse to the bottom. Therefore, the total unique paths at grid (r,c) is equal to the sum of total unique paths from the grid to the right and the grid below. Below is the backtracking code in 5 lines of code:

int backtrack(int r, int c, int m, int n) {
  if (r == m && c == n)
    return 1;
  if (r > m || c > n)
    return 0;
 
  return backtrack(r+1, c, m, n) + backtrack(r, c+1, m, n);
}

Method 2 - 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].

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;  
  
}  

On a second thought, I see that in place of using a 2D matrix(paths) for memoization, we can just have 1-D array with length as width. Please see the code for the same as below.

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;  
}    

Complexity: Since we are traversing each element just once, this solution has linear time complexity.

Method 3 - Treating it as counting problem
Our argument is based on three observations:

1. all the paths have size $2\times n$ (the reason is obvious: you have to go right $n$ positions and down another $n$ positions);
2. since we can only go right or down, we can identify every path by a string of Rs and Ds, where a R means going right and a D means going down; as an example, the paths illustrated in the problem statement are (from left to right and from top to bottom): RRDD, RDRD, RDDR, DRRD, DRDR and DDRR;
3. the strings mentioned above must contain the same number of Rs and Ds.

From these three observations, we can transform the problem to the following:

How many different strings of size $2\times n$, consisting of $n$ Rs and n Ds, are there?

The solution is now very simple, because the positioning of $n$ Ds (or Rs) determines the positioning of the other $n$ Rs (or Ds). Hence, the number we are interested in is the number of ways in which we can choose $n$ positions from $2\times n$ available positions. The answer, using the traditional notation for the binomial coefficient, is:

$$\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=\frac{(2n)!}{n!\times n!}.$$

Instantiating n with 20, we get the answer to the initial problem of the $20\times 20$ grid.

Generalization to $m\times n$ grids

The generalization to an $m\times n$ grid is also simple. The only difference is that the strings have length $m+n$. Using the same reasoning as above, the number of paths through an $m\times n$ grid is:

$$\left(\genfrac{}{}{0ex}{}{m+n}{n}\right)=\frac{(m+n)!}{m!\times n!}.$$

References - 1,2