# Number of Paths

let's go through the question:-

For convenience, let’s represent every square in the grid as a pair `(i,j)`

. The first coordinate in the pair denotes the east-to-west axis, and the second coordinate denotes the south-to-north axis. The initial state of the car is `(0,0)`

, and the destination is `(n-1,n-1)`

.

The car must abide by the following two rules: it cannot cross the diagonal border. In other words, in every step the position `(i,j)`

needs to maintain `i >= j`

. See the illustration above for `n = 5`

. In every step, it may go one square North (up), or one square East (right), but not both. E.g. if the car is at `(3,1)`

, it may go to `(3,2)`

or `(4,1)`

.

You’re testing a new driverless car that is located at the Southwest (bottom-left) corner of an `n×n`

grid. The car is supposed to get to the opposite, Northeast (top-right), corner of the grid. Given `n`

, the size of the grid’s axes, write a function `numOfPathsToDest`

that returns the number of the possible paths the driverless car can take.

input: n = 4

output: 5

# since there are five possibilities:# “EEENNN”, “EENENN”, “ENEENN”, “ENENEN”, “EENNEN”,# where the ‘E’ character stands for moving one step# East, and the ’N’ character stands for moving one step# North (so, for instance, the path sequence “EEENNN”# stands for the following steps that the car took:# East, East, East, North, North, North)

ans:-

#include <iostream>

#include <vector>

using namespace std;

// compexity O(n2)

int numOfPathsToDest( int n )

{ vector<vector<int>> vec(n,vector<int>(n,0)); //for dp

for(int i=0;i<n;i++)

vec[0][i]=1;

for(int i=1;i<n;i++){

for(int j=i;j<n;j++){

vec[i][j] = vec[i][j-1] + vec[i-1][j];

}

}

return vec[n-1][n-1];

}//driver codeint main(){cout<<numOfPathsToDest(4);return 0;}

You can directly view the code here:-

Happy Coding!!

#CodeWithKaran