Algotree > Algorithms > Dynamic Programming > Finding All Unique Paths From Top-Left To Bottom-Right Corner

Finding All Unique Paths From Top-Left To Bottom-Right Corner

All_Unique_Paths Problem Statement : Find the number of unique paths from source to destination in a grid, given conditions

Your initial position is the top-left corner of the grid i.e grid [ 0 ] [ 0 ].
Your destination is the bottom-right corner of the grid i.e grid [ r - 1 ] [ c - 1 ].
One can only take a path to the right of the current cell or a path below the current cell.

The idea behind this algorithm is quite simple.

For all the cells in the top-most row, there is only one path from the left to reach each of them as one cannot reach these cells from above.
For all the cells in the left-most column, there is only one path from above to reach each of them as one cannot reach these cells from the left.
For all the remaining cells at position [ r ] [ c ] one can reach from the left cell
i.e at postion [ r ] [ c - 1 ] or from the cell above at position [ r - 1 ] [ c ].

Recursive Algorithm : UniquePaths ( row, column )

If row < 0 or column < 0 then
     [ As there cannot be any paths coming from the left of 0’th column
     or any paths coming from the top of the 0’th row. ]
     return 0
If row equals 0 or column equals 0 then
     [ As there is only one path in the 0’th column
     and only one path in the 0’th row. ]
     return 1
For all the other cells that are not in the leftmost column and topmost row
return UniquePaths ( row - 1, column ) + UniquePaths ( row, column - 1 )

C++ Finding all unique paths in a grid using recursion

#include<iostream>

using namespace std;

int Unique_Paths (int row, int col) {

    // If the row or column number is less than 0, i.e if we must 
    // have stepped beyond the grid so there is no path to be found.
    if (row < 0 or col < 0)
        return 0;

    // There is only one path going through the topmost row and leftmost column
    if (row == 0 || col == 0) {
        return 1;
    }   
 
    // For all the other cells not in topmost row and leftmost column
    // The number of paths is the addtion of paths from the cell above and cell
    // to the left of the current cell.
    return Unique_Paths (row - 1, col) + Unique_Paths (row, col - 1); 
}

int main() {

    int rows = 7, cols = 3, paths;

    paths = Unique_Paths(rows-1, cols-1);
    cout << "Grid Rows : " << rows << " Columns : " << cols << " Paths : " << paths << endl;

    rows = 3, cols = 3;

    paths = Unique_Paths(rows-1, cols-1);
    cout << "Grid Rows : " << rows << " Columns : " << cols << " Paths : " << paths << endl;

    return 0;
}

Output

Grid Rows : 7 Columns : 3 Paths : 28
Grid Rows : 3 Columns : 3 Paths : 6

Dynamic Programming Algorithm : UniquePaths ( rows, cols )

Base Case : Initialize the elements in the first row and first column of the grid to 1
as there is only one path to reach each cell in the top-most row and left-most column.
For all columns c of the first row we assign grid [ 0 ] [ c ] = 1
For all rows r of the first column we assign grid [ r ] [ 0 ] = 1
All the other cells of the grid can either be reached from the cell above or from the cell to the left. Thus,
For each row r in the grid :
     For each column c in the grid :
           Path to current cell at [ r ] [ c ] = Path from the cell above at position [ r - 1 ] [ c ] + Path from the cell to the left at position [ r ] [ c - 1 ]
           i.e grid [ r ] [ c ] = grid [ r - 1 ] [ c ] + grid [ r ] [ c - 1 ]

Time complexity : O ( m * n ), where m is the number of rows and n is the number of columns in the grid.

C++ program to find all unique paths in a grid using dynamic programming

#include<iostream>

using namespace std;

int UniquePaths (int m, int n) {
 
    int grid[m][n];
 
    cout << "Grid Rows : " << m << ", Columns : " << n << endl;

    // All elements of 1'st column = 1
    for (int r = 0; r < m ; r++)
        grid[r][0] = 1;

    // All elements of 1'st row = 1
    for (int c = 0; c < n ; c++)
        grid[0][c] = 1;
   
    for (int r = 1; r < m ; r++) {
        for (int c = 1; c < n; c++) {
            grid[r][c] = grid[r-1][c] + grid[r][c-1];
        }   
    }   
 
    return grid[m-1][n-1];    
}

int main() {

    int rows = 7, cols = 3, paths;
    paths = UniquePaths(rows, cols);
    cout << "Paths : " << paths << endl;

    rows = 3, cols = 3;
    paths = UniquePaths(rows, cols);
    cout << "Paths : " << paths << endl;

    return 0;
}

Output

Grid Rows : 7, Columns : 3
Paths : 28
Grid Rows : 3, Columns : 3
Paths : 6