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