Last Updated: 14 Sep, 2021
Lakshay and Manik
Moderate
Asked in company
Lakshay and Manik met on an online chatting platform. Due to their shared interest in problem-solving, they became good friends. One day Lakshay decided to meet Manik. Manik lives in a small town at (0, N - 1) on a square matrix of N * N, and Lakshay lives at (N - 1, 0). As they are fond of problem-solving, Manik wants to know how many ways Lakshay can reach him. Help Lakshay to find out how many possible paths are there to reach Manik.
Lakshay can move Up(j, k) -> (j - 1, k), RIght(j, k) -> (j, k + 1) or Up-Right(j, k) -> (j - 1, k + 1).
Answers can be very large, so return the answer modulo 1000000007.
For Example :
N = 2
For n = 2, there can be three possible moves, as shown in the figure. Hence the answer is 3.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’ denoting the size of the square matrix.
Output Format :
For each test case, print a single integer “ans” denoting the total number of paths.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 500
Time limit: 1 sec
Approaches
In this approach, we will start from the (N - 1, 0) and add all the possible paths for down, left, and down-left.
The steps are as follows:
- In the “main” function:
- Return the function recursion and pass the value of ‘N’ as ‘x’ and one as ‘y’.
- In the “recursion” function:
- If x equals to 1 or y equals to N, return 1.
- Else take a variable “ans” to store the answer.
- Update “ans” = (recursion(x - 1, y) + recursion(x, y + 1) + recursion(x - 1, y + 1)) % 1000000007.
- Return “ans”.
In this approach, we will start from the (N - 1, 0) and add all the possible paths for down, left, and down-left and store all the values in a 2D array “dp”.
The steps are as follows:
- In the “main” function:
- Take a 2D array “dp”, and initialize it with -1.
- Return the function “topDownDP” and pass the value of ‘N’ as ‘x’ and one as ‘y’, and the array dp.
- In the “topDownDP” function:
- If x equals to 1 or y equals to N, return 1.
- Else take a pointer “ans” pointing to “dp[x][y]” .
- If dp[x][y] is not equal to -1, return “dp[x][y]”.
- Update “ans” = (topDownDP(x - 1, y) + topDownDP(x, y + 1) + topDownDP(x - 1, y + 1)) % 1000000007.
- Return “ans”.
In this approach, we will take a 2D array “dp”, where “dp[i][j]” will store the total number of paths from (n - 1, 0) to (i, j).
The steps are as follows:
- Take a 2D array “dp”.
- Iterate through the loop from 0 to n - 1(say iterator be i):
- Update dp[i][0] = 1 and dp[0][i] = 1.
- Iterate through the loop from 0 to n-1(say iterator be i):
- Iterate through the loop from 0 to n - 1(say iterator be j):
- Update dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]) % 1000000007.
- Iterate through the loop from 0 to n - 1(say iterator be j):
- Return dp[n - 1][n - 1].