Problem Explanation
We are given a m \times n grid. We start at the top left square (0, 0) in the grid and have to reach the bottom right square (n-1, m-1). In a move we can only move right or down. We have to tell the number of possible paths we can take modulo 10^9+7.
Approach
At any given square we can be sure that the only way to reach it is from the top or left (as we can only travel right or down). Thus the number of ways to reach a certain square is the sum of number of ways to reach the square above it and the number of ways to reach the square on it’s left. As for the base condition, if we are in the top row, then there will be no square on top of it. So there can be only one way to reach a square in the top row(from the left). Similarly for the squares in the leftmost column, they can only be reached from the square above. Thus, they also will have only 1 path. Like this, we can work our way down the grid till the bottom-right square and then output the number of paths to the bottom right square
Code
#include <bits/stdc++.h>
using namespace std;
const int M = 1e9+7;
int main() {
int t;
cin>>t;
while(t--){
long long n, m;
cin>>n>>m;
vector<vector<long long>> dp(n, vector<long long> (m));
for(int i=0; i<n; i++){
dp[i][0] = 1;
}
for(int i=0; i<m; i++){
dp[0][i] = 1;
}
for(int i=1; i<n; i++){
for(int j=1; j<m; j++){
dp[i][j] = dp[i-1][j]%M + dp[i][j-1]%M;
dp[i][j] %= M;
}
}
cout<<dp[n-1][m-1]<<endl;
}
}