Number of ways to reach from a starting position to an ending position in C++

In this tutorial, we are going to learn how to find the Number of ways to reach from a starting position to an ending position in a matrix type path in C++, considering we can only travel rightward and downward. This problem is a standard dynamic programming problem.

To reach a  particular cell (i,j), one must first reach either the cell (i-1,j) or the cell (i,j-1) and then move one step down or to the right respectively to reach cell (i,j). We will try to formulate a bottom-up dynamic programming solution.  We will have to use the following recurrence relation:

numofWays(i,j) = numofWays(i-1,j) + numofWays(i,j-1)

Now, we need to find out the base cases and the rest will be calculated by the following relation. Considering a 2×2 matrix:

We can travel either through (0,0) -> (0,1) -> (1,1) or (0,0) -> (1,0) -> (1,1). So the total number of ways will be two. Now let us try to implement this idea in our code to get the required answer.

C++ Program to find the Number of ways to reach from a starting position to an ending position

Cpp source code:

// Program to find Number of ways to reach from a starting position to an ending position
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int x,y;
    cout<<"Enter number of rows and columns :";
    cin>>x>>y;
    int NumofWays[x][y]; // Declaring table to store previous values which we have travelled
    NumofWays[0][0] = 1;
    
    // Declaring base case
    for(int i=1;i<x;i++)
    {
    	NumofWays[i][0] = 1;
  }
  
  // Declaring base case
    for(int i=1;i<y;i++)
    {
    	NumofWays[0][i] = 1;
    }
       
  // Bottom up approach to solve this problem
    for(int i=1;i<x;i++)
  {
    for(int j=1;j<y;j++)
    {
      NumofWays[i][j] = NumofWays[i-1][j] + NumofWays[i][j-1];
    }
  }
 
    cout<<"Number of ways from(0,0) to ending positon is "<<NumofWays[x-1][y-1];
    return 0;
}

Input/Output:

Enter number of rows and columns :3 3
Number of ways from(0,0) to ending position is 6

The time complexity of this program is o( n*n).

Also check:

Travelling Salesperson Problem using Dynamic Approach in C++

Activity Selection Problem using Greedy method in C++

Do not forget to comment if you find anything wrong in the post or if you want to share some information regarding the same.