# Count all possible paths from top left to bottom right

The task is to count all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down.count of all the possible paths from top left to bottom right of a mXn matrix. Since output can be very large number use %10^9+7.

ex:

i)4 4 //matrix of size 4*4

answer is 20 // all the possible paths from top left to bottom right

ii) 3 3 //matrix of size 3*3

answer is 6 // all the possible paths from top left to bottom right

we will use dynamic programming here:

c++ implementation:

y is the no. of test cases:

ex:

i)4 4 //matrix of size 4*4

answer is 20 // all the possible paths from top left to bottom right

ii) 3 3 //matrix of size 3*3

answer is 6 // all the possible paths from top left to bottom right

we will use dynamic programming here:

c++ implementation:

y is the no. of test cases:

**#include <iostream>
using namespace std;
void count(int n,int w)
{
int t[n][w];
for(int i=0;i<n;i++)
t[i][0]=1;
for(int j=0;j<w;j++)
t[0][j]=1;
for(int i=1;i<n;i++)
for(int j=1;j<w;j++)
t[i][j]=(t[i-1][j]+t[i][j-1])% 1000000007;
//max value will b present in last cell
cout<<(t[n-1][w-1])% 1000000007 ;
}
int main() {
int y; cin>>y;
while(y--)
{ int n; int w;
cin>>n>>w;
count(n,w);
cout<<endl;
}
return 0;
}**