Given 2 integers M and N, the task is to find the count of all the possible paths from top left to the bottom right of an M x N matrix with the constraints that from each cell you can either move only to right or down or diagonally
Examples:
Input: M = 3, N = 3
Output: 13
Explanation: There are 13 paths as follows: VVHH, VHVH, HVVH, DVH, VDH, VHHV, HVHV, DHV, HHVV, HDV, VHD, HVD, and DD where V represents vertical, H represents horizontal, and D represents diagonal paths.Input: M = 2, N = 2
Output: 3
Approach: The idea is to use recursion to find the total number of paths. This approach is very similar to the one discussed in this article. Follow the steps below to solve the problem:
- If M or N equals 1, then return 1.
- Else create a recursive function numberOfPaths() call the same function for values {M-1, N}, {M, N-1} and {M-1, N-1} representing vertical, horizontal and diagonal movement respectively.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Returns count of possible paths to// reach cell at row number M and column// number N from the topmost leftmost// cell (cell at 1, 1)int numberOfPaths(int M, int N){ // If either given row number or // given column number is first if (M == 1 || N == 1) return 1; // Horizontal Paths + // Vertical Paths + // Diagonal Paths return numberOfPaths(M - 1, N) + numberOfPaths(M, N - 1) + numberOfPaths(M - 1, N - 1);}// Driver Codeint main(){ cout << numberOfPaths(3, 3); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG{ // Returns count of possible paths to// reach cell at row number M and column// number N from the topmost leftmost// cell (cell at 1, 1)static int numberOfPaths(int M, int N){ // If either given row number or // given column number is first if (M == 1 || N == 1) return 1; // Horizontal Paths + // Vertical Paths + // Diagonal Paths return numberOfPaths(M - 1, N) + numberOfPaths(M, N - 1) + numberOfPaths(M - 1, N - 1);}// Driver Codepublic static void main(String args[]){ System.out.print(numberOfPaths(3, 3));}}// This code is contributed by Samim Hossain Mondal. |
Python
# Python program for the above approach# Returns count of possible paths to# reach cell at row number M and column# number N from the topmost leftmost# cell (cell at 1, 1)def numberOfPaths(M, N): # If either given row number or # given column number is first if (M == 1 or N == 1): return 1 # Horizontal Paths + # Vertical Paths + # Diagonal Paths return numberOfPaths(M - 1, N) \ + numberOfPaths(M, N - 1) \ + numberOfPaths(M - 1, N - 1)# Driver Codeprint(numberOfPaths(3, 3))# This code is contributed by Samim Hossain Mondal. |
C#
// C# program for the above approachusing System;public class GFG{ // Returns count of possible paths to// reach cell at row number M and column// number N from the topmost leftmost// cell (cell at 1, 1)static int numberOfPaths(int M, int N){ // If either given row number or // given column number is first if (M == 1 || N == 1) return 1; // Horizontal Paths + // Vertical Paths + // Diagonal Paths return numberOfPaths(M - 1, N) + numberOfPaths(M, N - 1) + numberOfPaths(M - 1, N - 1);}// Driver Codepublic static void Main(String []args){ Console.Write(numberOfPaths(3, 3));}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code for the above approach // Returns count of possible paths to // reach cell at row number M and column // number N from the topmost leftmost // cell (cell at 1, 1) function numberOfPaths(M, N) { // If either given row number or // given column number is first if (M == 1 || N == 1) return 1; // Horizontal Paths + // Vertical Paths + // Diagonal Paths return numberOfPaths(M - 1, N) + numberOfPaths(M, N - 1) + numberOfPaths(M - 1, N - 1); } // Driver Code document.write(numberOfPaths(3, 3)); // This code is contributed by Potta Lokesh </script> |
Output
13
Time Complexity: O(3M*N)
Auxiliary Space: O(N), where N is recursion stack space.
Efficient Approach: Dp (using Memoization)
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;static int dp[1001][1001];// Returns count of possible paths to// reach cell at row number M and column// number N from the topmost leftmost// cell (cell at 1, 1)int numberOfPaths(int M, int N){ // If either given row number or // given column number is first if (M == 1 || N == 1) return 1; // If a value already present // in t[][], return it if(dp[M][N] != -1) { return dp[M][N]; } // Horizontal Paths + // Vertical Paths + // Diagonal Paths return dp[M][N] = numberOfPaths(M - 1, N) + numberOfPaths(M, N - 1) + numberOfPaths(M - 1, N - 1);}// Driver Codeint main(){ memset(dp,-1,sizeof(dp)); cout << numberOfPaths(3, 3); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG { static int[][] dp = new int[1001][1001]; // Returns count of possible paths to // reach cell at row number M and column // number N from the topmost leftmost // cell (cell at 1, 1) static int numberOfPaths(int M, int N) { // If either given row number or // given column number is first if (M == 1 || N == 1) return 1; // If a value already present // in t[][], return it if (dp[M][N] != -1) { return dp[M][N]; } // Horizontal Paths + // Vertical Paths + // Diagonal Paths dp[M][N] = numberOfPaths(M - 1, N) + numberOfPaths(M, N - 1) + numberOfPaths(M - 1, N - 1); return dp[M][N]; } // Driver Code public static void main(String args[]) { for (int i = 0; i < 1001; i++) for (int j = 0; j < 1001; j++) dp[i][j] = -1; System.out.println(numberOfPaths(3, 3)); }}// This code is contributed by Samim Hossain Mondal. |
Python
# Python program for the above approach# Taking the matrix as globallydp = [[-1 for i in range(1001)] for j in range(1001)]# Returns count of possible paths to# reach cell at row number M and column# number N from the topmost leftmost# cell (cell at 1, 1)def numberOfPaths(M, N): # If either given row number or # given column number is first if (M == 1 or N == 1): return 1 # If a value already present # in t[][], return it if(dp[M][N] != -1): return dp[M][N] # Horizontal Paths + # Vertical Paths + # Diagonal Paths dp[M][N] = numberOfPaths(M - 1, N) + numberOfPaths(M, N - 1) + numberOfPaths(M - 1, N - 1) return dp[M][N]# Driver Codeprint(numberOfPaths(3, 3))# This code is contributed by Samim Hossain Mondal. |
C#
// C# program for the above approachusing System;class GFG { static int[, ] dp = new int[1001, 1001]; // Returns count of possible paths to // reach cell at row number M and column // number N from the topmost leftmost // cell (cell at 1, 1) static int numberOfPaths(int M, int N) { // If either given row number or // given column number is first if (M == 1 || N == 1) return 1; // If a value already present // in t[][], return it if (dp[M, N] != -1) { return dp[M, N]; } // Horizontal Paths + // Vertical Paths + // Diagonal Paths dp[M, N] = numberOfPaths(M - 1, N) + numberOfPaths(M, N - 1) + numberOfPaths(M - 1, N - 1); return dp[M, N]; } // Driver Code public static void Main() { for (int i = 0; i < 1001; i++) for (int j = 0; j < 1001; j++) dp[i, j] = -1; Console.Write(numberOfPaths(3, 3)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program of the above approach var dp = new Array(1001); // Loop to create 2D array using 1D array for (var i = 0; i < dp.length; i++) { dp[i] = new Array(1001); } // Returns count of possible paths to // reach cell at row number M and column // number N from the topmost leftmost // cell (cell at 1, 1) function numberOfPaths(M, N) { // If either given row number or // given column number is first if (M == 1 || N == 1) return 1; // If a value already present // in t[][], return it if (dp[M][N] != -1) { return dp[M][N]; } // Horizontal Paths + // Vertical Paths + // Diagonal Paths dp[M][N] = numberOfPaths(M - 1, N) + numberOfPaths(M, N - 1) + numberOfPaths(M - 1, N - 1); return dp[M][N]; } // Driver Code for (let i = 0; i < 1001; i++){ for (let j = 0; j < 1001; j++){ dp[i][j] = -1; }} document.write(numberOfPaths(3, 3));// This code is contributed by avijitmondal1998 </script> |
Output
13
Time Complexity: O(M*N), The time complexity of this approach is O(M*N). Since there are MN subproblems, and each subproblem takes constant time to solve. This is because the solution to each subproblem is a sum of three previously computed subproblems. Therefore, the total time taken is proportional to the number of subproblems, which is M*N.
Auxiliary Space: O(M*N), The space complexity of this approach is also O(M*N). This is because we are using a two-dimensional array of size (M+1) * (N+1) to store the results of the subproblems. Each cell of this array requires constant space, and hence the total space required is proportional to the number of subproblems, which is M*N.
Efficient Approach: Dp (using Tables)
Follow below steps to solve the problem using bottom up approach:
- Initialize dp[1][1] = 1 and dp[1][1..N-1] = 1, dp[1..M-1][1] = 1
- For each i = 1 to M, do the following:
a. For each j = 1 to N, do the following:
i. Compute dp[i][j] as dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1] - Return dp[M][N]
Below is the implementation of the approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Returns count of possible paths to// reach cell at row number M and column// number N from the topmost leftmost// cell (cell at 1, 1)int numberOfPaths(int M, int N) { // Initialize a 2D array to store // intermediate results of subproblems int dp[M + 1][N + 1]; // Set all elements of dp to 1 // as there is only one path // to reach any cell in the first // row or column for (int i = 1; i <= M; i++) { for (int j = 1; j <= N; j++) { if (i == 1 || j == 1) { dp[i][j] = 1; } } } // Fill the dp array using bottom-up // approach for (int i = 2; i <= M; i++) { for (int j = 2; j <= N; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]; } } // Return the value stored at dp[M][N] return dp[M][N];}// Driver codeint main() { // Function Call cout << numberOfPaths(3, 3); return 0;}// This code is contributed by Chandramani Kumar |
Java
import java.util.Arrays;public class GFG { static int numberOfPaths(int m, int n) { // Initialize a 2D array to store // intermediate results of subproblems int[][] dp = new int[m + 1][n + 1]; // Set all elements of dp to 1 // as there is only one path // to reach any cell in the first // row or column for (int i = 0; i <= m; i++) { Arrays.fill(dp[i], 1); } // Fill the dp array using bottom-up // approach for (int i = 2; i <= m; i++) { for (int j = 2; j <= n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]; } } // Return the value stored at dp[M][N] return dp[m][n]; } public static void main(String[] args) { // Function Call System.out.println(numberOfPaths(3, 3)); }} |
Python
# Python program for the above approach# Function to return count of possible paths to reach# cell at row number m and column number n from the# topmost leftmost cell (cell at 1, 1)def numberOfPaths(m, n): # Create a 2D table to store results of subproblems dp = [[0 for x in range(n+1)] for x in range(m+1)] # Set all elements of dp to 1 as there is only one # path to reach any cell in the first row or column for i in range(m+1): for j in range(n+1): if i == 1 or j == 1: dp[i][j] = 1 # Calculate count of paths for other cells in bottom-up manner for i in range(2, m+1): for j in range(2, n+1): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1] return dp[m][n]# Driver program to test above functionm = 3n = 3print(numberOfPaths(m, n))# This code is contributed by Tapesh(tapeshdua420) |
C#
// C# implmentationusing System;class GFG { static int numberOfPaths(int m, int n) { // Initialize a 2D array to store // intermediate results of subproblems int[, ] dp = new int[m + 1, n + 1]; // Set all elements of dp to 1 // as there is only one path // to reach any cell in the first // row or column for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { dp[i, j] = 1; } } // Fill the dp array using bottom-up // approach for (int i = 2; i <= m; i++) { for (int j = 2; j <= n; j++) { dp[i, j] = dp[i - 1, j] + dp[i, j - 1] + dp[i - 1, j - 1]; } } // Return the value stored at dp[M][N] return dp[m, n]; } static void Main(string[] args) { // Function Call Console.WriteLine(numberOfPaths(3, 3)); Console.ReadKey(); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
function numberOfPaths(M, N) { // Initialize a 2D array to store let dp = new Array(M + 1).fill(0).map(() => new Array(N + 1).fill(0)); // Set all elements of dp to 1 // as there is only one path // to reach any cell in the first // row or column for (let i = 1; i <= M; i++) { for (let j = 1; j <= N; j++) { if (i === 1 || j === 1) { dp[i][j] = 1; } } } for (let i = 2; i <= M; i++) { for (let j = 2; j <= N; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]; } } return dp[M][N];}// Driver code // Function Call console.log(numberOfPaths(3, 3)); |
Output
13
Time Complexity: O(M*N) as two nested loops are executing one from 1 to M and other from 1 to N where M and N are rows and columns respectively.
Space Complexity: O(M*N) as 2D array dp has been created of size M+1 and N+1 where M and N are rows and columns respectively.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
