When your main ideas show a right to left or top to bottom direction you are using a problem solution pattern?

Read

Discuss

View Discussion

Improve Article

Save Article

Like Article

The problem 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
Examples :

Input : m = 2, n = 2; Output : 2 There are two paths (0, 0) -> (0, 1) -> (1, 1) (0, 0) -> (1, 0) -> (1, 1) Input : m = 2, n = 3; Output : 3 There are three paths (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) (0, 0) -> (1, 0) -> (1, 1) -> (1, 2)

We have discussed a solution to print all possible paths, counting all paths is easier. Let NumberOfPaths(m, n) be the count of paths to reach row number m and column number n in the matrix, NumberOfPaths(m, n) can be recursively written as following.

Implementation:

#include <iostream>
using namespace std;
int numberOfPaths(int m, int n)
{
    if (m == 1 || n == 1)
        return 1;
    return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);
}
int main()
{
    cout << numberOfPaths(3, 3);
    return 0;
}

class GFG {
    static int numberOfPaths(int m, int n)
    {
        if (m == 1 || n == 1)
            return 1;
        return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);
    }
    public static void main(String args[])
    {
        System.out.println(numberOfPaths(3, 3));
    }
}

def numberOfPaths(m, n):
    if(m == 1 or n == 1):
        return 1
    return numberOfPaths(m-1, n) + numberOfPaths(m, n-1)
m = 3
n = 3
print(numberOfPaths(m, n))

using System;
public class GFG {
    static int numberOfPaths(int m, int n)
    {
        if (m == 1 || n == 1)
            return 1;
        return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);
    }
    static public void Main()
    {
        Console.WriteLine(numberOfPaths(3, 3));
    }
}

<?php
function numberOfPaths($m, $n)
{
    if ($m == 1 || $n == 1)
            return 1;
    return numberOfPaths($m - 1, $n) +
           numberOfPaths($m, $n - 1);
}
echo numberOfPaths(3, 3);
?>

<script>
    function numberOfPaths(m, n)
    {
        if (m == 1 || n == 1)
            return 1;
        return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);
    }
    document.write(numberOfPaths(3, 3)+"<br>");
</script>

The time complexity of above recursive solution is exponential – O(2^n). There are many overlapping subproblems. We can draw a recursion tree for numberOfPaths(3, 3) and see many overlapping subproblems. The recursion tree would be similar to Recursion tree for Longest Common Subsequence problem.

So this problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array count[][] in bottom up manner using the above recursive formula.

Implementation:

#include <iostream>
using namespace std;
int numberOfPaths(int m, int n)
{
    int count[m][n];
    for (int i = 0; i < m; i++)
        count[i][0] = 1;
    for (int j = 0; j < n; j++)
        count[0][j] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++)
            count[i][j] = count[i - 1][j] + count[i][j - 1]; 
    }
    return count[m - 1][n - 1];
}
int main()
{
    cout << numberOfPaths(3, 3);
    return 0;
}

class GFG {
    static int numberOfPaths(int m, int n)
    {
        int count[][] = new int[m][n];
        for (int i = 0; i < m; i++)
            count[i][0] = 1;
        for (int j = 0; j < n; j++)
            count[0][j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++)
                count[i][j] = count[i - 1][j] + count[i][j - 1]; 
        }
        return count[m - 1][n - 1];
    }
    public static void main(String args[])
    {
        System.out.println(numberOfPaths(3, 3));
    }
}

def numberOfPaths(m, n):
    count = [[0 for x in range(n)] for y in range(m)]
    for i in range(m):
        count[i][0] = 1;
    for j in range(n):
        count[0][j] = 1;
    for i in range(1, m):
        for j in range(1, n):            
            count[i][j] = count[i-1][j] + count[i][j-1]
    return count[m-1][n-1]
m = 3
n = 3
print( numberOfPaths(m, n))

using System;
public class GFG {
    static int numberOfPaths(int m, int n)
    {
        int[, ] count = new int[m, n];
        for (int i = 0; i < m; i++)
            count[i, 0] = 1;
        for (int j = 0; j < n; j++)
            count[0, j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++)
                count[i, j] = count[i - 1, j] + count[i, j - 1]; 
        }
        return count[m - 1, n - 1];
    }
    static public void Main()
    {
        Console.WriteLine(numberOfPaths(3, 3));
    }
}

<?php
function numberOfPaths($m, $n)
{
    $count = array();
    for ($i = 0; $i < $m; $i++)
        $count[$i][0] = 1;
    for ($j = 0; $j < $n; $j++)
        $count[0][$j] = 1;
    for ($i = 1; $i < $m; $i++)
    {
        for ($j = 1; $j < $n; $j++)
            $count[$i][$j] = $count[$i - 1][$j] +
                             $count[$i][$j - 1]; 
    }
    return $count[$m - 1][$n - 1];
}
echo numberOfPaths(3, 3);
?>

<script>
function numberOfPaths(m , n)
{
    var count = Array(m).fill(0).map(x => Array(n).fill(0));
    for (i = 0; i < m; i++)
        count[i][0] = 1;
    for (j = 0; j < n; j++)
        count[0][j] = 1;
    for (i = 1; i < m; i++) {
        for (j = 1; j < n; j++)
            count[i][j] = count[i - 1][j] + count[i][j - 1];
    }
    return count[m - 1][n - 1];
}
document.write(numberOfPaths(3, 3));
</script>

Time Complexity: O(M*N) – Due to nested for loops.
Auxiliary Space : O(M*N) – We have used a 2D array of size MxN.

Recursive Dynamic Programming solution. The following implementation is based on the Top-Down approach.

#include <iostream>
#include <cstring>
using namespace std;
int numberOfPaths(int n,int m,int DP[4][4]){
    if(n == 1 || m == 1)
        return DP[n][m] = 1;
    if(DP[n][m] == 0)
        DP[n][m] = numberOfPaths(n - 1, m,DP) + numberOfPaths(n, m - 1,DP);
    return DP[n][m];
}
int main()
{
    int DP[4][4] = {0};
    memset(DP, 0, sizeof(DP));
    cout << numberOfPaths(3, 3,DP);
    return 0;
}

import java.util.*;
public class GFG
{
    static int numberOfPaths(int n, int m, int DP[][])
    {
        if (n == 1 || m == 1)
            return DP[n][m] = 1;
        if (DP[n][m] == 0)
            DP[n][m] = numberOfPaths(n - 1, m, DP)
                       + numberOfPaths(n, m - 1, DP);
        return DP[n][m];
    }
    public static void main(String args[])
    {
        int DP[][] = new int[4][4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                DP[i][j] = 0;
            }
        }
        System.out.println(numberOfPaths(3, 3, DP));
    }
}

def numberOfPaths(n, m, DP):
    if (n == 1 or m == 1):
        DP[n][m] = 1;
        return  1;
    if (DP[n][m] == 0):
        DP[n][m] = numberOfPaths(n - 1, m, DP) + numberOfPaths(n, m - 1, DP);
    return DP[n][m];
if __name__ == '__main__':
    DP = [[0 for i in range(4)] for j in range(4)] ;
    print(numberOfPaths(3, 3, DP));

using System;
class GFG {
    static int numberOfPaths(int n, int m, int[, ] DP)
    {
        if (n == 1 || m == 1)
            return DP[n, m] = 1;
        if (DP[n, m] == 0)
            DP[n, m] = numberOfPaths(n - 1, m, DP)
                       + numberOfPaths(n, m - 1, DP);
        return DP[n, m];
    }
    public static void Main()
    {
        int[, ] DP = new int[4, 4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                DP[i, j] = 0;
            }
        }
        Console.WriteLine(numberOfPaths(3, 3, DP));
    }
}

<script>
let DP = new Array(4);
for(let i = 0; i < 4; i++) {
    DP[i] = new Array(4);
    for(let j = 0; j < 4; j++) {
        DP[i][j] = 0;
    }
}
function numberOfPaths(n, m, DP){
    if(n == 1 || m == 1)
        return DP[n][m] = 1;
    if(DP[n][m] == 0)
        DP[n][m] = numberOfPaths(n - 1, m,DP) + numberOfPaths(n, m - 1,DP);
    return DP[n][m];
}
document.write(numberOfPaths(3, 3,DP));
</script>

Time complexity of the above 2 dynamic programming solutions is O(mn). The space complexity of the above 2 solutions is O(mn) required for the 2D array.

Space Optimization of DP solution.

Above solution is more intuitive but we can also reduce the space by O(n); where n is column size.
Implementation:

#include <bits/stdc++.h>
using namespace std;
int numberOfPaths(int m, int n)
{
    int dp[n] = { 1 };
    dp[0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}
int main()
{
    cout << numberOfPaths(3, 3);
}

class GFG {
    static int numberOfPaths(int m, int n)
    {
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
    public static void main(String args[])
    {
        System.out.println(numberOfPaths(3, 3));
    }
}

def numberOfPaths(p, q):
    dp = [1 for i in range(q)]
    for i in range(p - 1):
        for j in range(1, q):
            dp[j] += dp[j - 1]
    return dp[q - 1]
print(numberOfPaths(3, 3))

using System;
class GFG {
    static int numberOfPaths(int m, int n)
    {
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
    public static void Main()
    {
        Console.Write(numberOfPaths(3, 3));
    }
}

<?php
function numberOfPaths($m, $n)
{
    $dp = array();
    $dp[0] = 1;
    for ($i = 0; $i < $m; $i++)
    {
    for ($j = 1; $j < $n; $j++)
    {
        $dp[$j] += $dp[$j - 1];
    }
    }
    return $dp[$n - 1];
}
echo numberOfPaths(3, 3);
?>

<script>
function numberOfPaths(m , n)
{
    dp = Array.from({length: n}, (_, i) => 0);
    dp[0] = 1;
    for (i = 0; i < m; i++) {
        for (j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}
document.write(numberOfPaths(3, 3));
</script>

Time Complexity: O(m*n)
Auxiliary Space: O(n)

This code is contributed by Vivek Singh

Note the count can also be calculated using the formula (m-1 + n-1)!/(m-1)!(n-1)!.

Another Approach: (Using combinatorics) In this approach We have to calculate m+n-2Cn-1 here which will be (m+n-2)! / (n-1)! (m-1)!

Now, let us see how this formula is giving the correct answer (Reference 1) (Reference 2) read reference 1 and reference 2 for a better understanding

m = number of rows, n = number of columns

Total number of moves in which we have to move down to reach the last row = m – 1 (m rows, since we are starting from (1, 1) that is not included)

Total number of moves in which we have to move right to reach the last column = n – 1 (n column, since we are starting from (1, 1) that is not included)

Down moves = (m – 1)
Right moves = (n – 1)

Total moves = Down moves + Right moves = (m – 1) + (n – 1)

Now think moves as a string of ‘R’ and ‘D’ character where ‘R’ at any ith index will tell us to move ‘Right’ and ‘D’ will tell us to move ‘Down’

Now think of how many unique strings (moves) we can make where in total there should be (n – 1 + m – 1) characters and there should be (m – 1) ‘D’ character and (n – 1) ‘R’ character?

Choosing positions of (n – 1) ‘R’ characters, results in automatic choosing of (m – 1) ‘D’ character positions

Calculate nCr
Number of ways to choose positions for (n – 1) ‘R’ character = Total positions C n – 1 = Total positions C m – 1 = (n – 1 + m – 1) !=

Another way to think about this problem: Count the Number of ways to make an N digit Binary String (String with 0s and 1s only) with ‘X’ zeros and ‘Y’ ones (here we have replaced ‘R’ with ‘0’ or ‘1’ and ‘D’ with ‘1’ or ‘0’ respectively whichever suits you better)

#include <iostream>
using namespace std;
int numberOfPaths(int m, int n)
{
    int path = 1;
    for (int i = n; i < (m + n - 1); i++) {
        path *= i;
        path /= (i - n + 1);
    }
    return path;
}
int main()
{
    cout << numberOfPaths(3, 3);
    return 0;
}

class GFG {
    static int numberOfPaths(int m, int n)
    {
        int path = 1;
        for (int i = n; i < (m + n - 1); i++) {
            path *= i;
            path /= (i - n + 1);
        }
        return path;
    }
    public static void main(String[] args)
    {
        System.out.println(numberOfPaths(3, 3));
    }
}

def numberOfPaths(m, n) :
    path = 1
    for i in range(n, (m + n - 1)):
        path *= i;
        path //= (i - n + 1);
    return path;
print(numberOfPaths(3, 3));

using System;
class GFG {
    static int numberOfPaths(int m, int n)
    {
        int path = 1;
        for (int i = n; i < (m + n - 1); i++) {
            path *= i;
            path /= (i - n + 1);
        }
        return path;
    }
    public static void Main()
    {
        Console.WriteLine(numberOfPaths(3, 3));
    }
}

<?php
function numberOfPaths($m, $n)
{
    $path = 1;
    for ($i = $n; $i < ($m + $n - 1); $i++)
    {
        $path *= $i;
        $path /= ($i - $n + 1);
    }
    return $path;
}
{
    echo(numberOfPaths(3, 3));
}

<script>
function numberOfPaths(m , n)
    {
        var path = 1;
        for (i = n; i < (m + n - 1); i++) {
            path *= i;
            path = parseInt(path/(i - n + 1));
        }
        return path;
    }
document.write(numberOfPaths(3, 3));
</script>

Time Complexity: O(m+n)

Auxiliary Space: O(1)

This article is contributed by Hariprasad NG. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.