Cuente todos los caminos posibles desde la parte superior izquierda hasta la parte inferior derecha de una array mXn

El problema es contar todos los caminos posibles desde la parte superior izquierda hasta la parte inferior derecha de una array mXn con las restricciones de que desde cada celda puede moverse solo hacia la derecha o hacia abajo
. Ejemplos: 

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)

Hemos discutido una solución para imprimir todas las rutas posibles , contar todas las rutas es más fácil. Sea NumberOfPaths(m, n) el recuento de rutas para alcanzar el número de fila m y el número de columna n en la array, NumberOfPaths(m, n) se puede escribir recursivamente de la siguiente manera.

Implementación:

// A C++  program to count all possible paths
// from top left to bottom right
 
#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 is first or given column
    // number is first
    if (m == 1 || n == 1)
        return 1;
 
    // If diagonal movements are allowed then the last
    // addition is required.
    return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);
    // + numberOfPaths(m-1, n-1);
}
 
int main()
{
    cout << numberOfPaths(3, 3);
    return 0;
}

// A Java program to count all possible paths
// from top left to bottom right
 
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 is first or
        // given column number is first
        if (m == 1 || n == 1)
            return 1;
 
        // If diagonal movements are allowed then
        // the last addition is required.
        return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);
        // + numberOfPaths(m-1, n-1);
    }
 
    public static void main(String args[])
    {
        System.out.println(numberOfPaths(3, 3));
    }
}
 
// This code is contributed by Sumit Ghosh

# Python program to count all possible paths
# from top left to bottom right
 
# 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):
# If either given row number is first
# or given column number is first
    if(m == 1 or n == 1):
        return 1
 
# If diagonal movements are allowed
# then the last addition
# is required.
    return numberOfPaths(m-1, n) + numberOfPaths(m, n-1)
 
# Driver program to test above function
m = 3
n = 3
print(numberOfPaths(m, n))
 
# This code is contributed by Aditi Sharma

// A C# program to count all possible paths
// from top left to bottom right
 
using 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 is first or
        // given column number is first
        if (m == 1 || n == 1)
            return 1;
 
        // If diagonal movements are allowed then
        // the last addition is required.
        return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);
        // + numberOfPaths(m-1, n-1);
    }
 
    static public void Main()
    {
        Console.WriteLine(numberOfPaths(3, 3));
    }
}
 
// This code is contributed by ajit

<?php
 
// 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
    // is first or given column
    // number is first
    if ($m == 1 || $n == 1)
            return 1;
     
    // If diagonal movements
    // are allowed then the last
    // addition is required.
    return numberOfPaths($m - 1, $n) +
           numberOfPaths($m, $n - 1);
}
 
// Driver Code
echo numberOfPaths(3, 3);
     
// This code is contributed by akt_mit
?>

<script>
// A Javascript program to count all possible paths
// from top left to bottom right
     
    // 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 is first or
        // given column number is first
        if (m == 1 || n == 1)
            return 1;
         
        // If diagonal movements are allowed then
        // the last addition is required.
        return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);
        
       // + numberOfPaths(m - 1, n - 1);
    }
     
    document.write(numberOfPaths(3, 3)+"<br>");
     
    // This code is contributed by rag2127
</script>

6

La complejidad temporal de la solución recursiva anterior es exponencial – O(2^n). Hay muchos subproblemas superpuestos. Podemos dibujar un árbol de recursión para numberOfPaths(3, 3) y ver muchos subproblemas superpuestos. El árbol de recurrencia sería similar al árbol de recurrencia para el problema de la subsecuencia común más larga . 

Así que este problema tiene las dos propiedades (ver this y this ) de un problema de programación dinámica. Al igual que otros problemas típicos de programación dinámica (DP) , los cálculos de los mismos subproblemas se pueden evitar mediante la construcción de una array temporal count[][] de forma ascendente utilizando la fórmula recursiva anterior.

Implementación:

// A C++ program to count all possible paths
// from top left to bottom right
#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)
{
    // Create a 2D table to store results of subproblems
    int count[m][n];
 
    // Count of paths to reach any cell in first column is 1
    for (int i = 0; i < m; i++)
        count[i][0] = 1;
 
    // Count of paths to reach any cell in first row is 1
    for (int j = 0; j < n; j++)
        count[0][j] = 1;
 
    // Calculate count of paths for other cells in
    // bottom-up manner using the recursive solution
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++)
 
            // By uncommenting the last part the code calculates the total
            // possible paths if the diagonal Movements are allowed
            count[i][j] = count[i - 1][j] + count[i][j - 1]; //+ count[i-1][j-1];
    }
    return count[m - 1][n - 1];
}
 
// Driver program to test above functions
int main()
{
    cout << numberOfPaths(3, 3);
    return 0;
}

// A Java program to count all possible paths
// from top left to bottom right
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)
    {
        // Create a 2D table to store results
        // of subproblems
        int count[][] = new int[m][n];
 
        // Count of paths to reach any cell in
        // first column is 1
        for (int i = 0; i < m; i++)
            count[i][0] = 1;
 
        // Count of paths to reach any cell in
        // first column is 1
        for (int j = 0; j < n; j++)
            count[0][j] = 1;
 
        // Calculate count of paths for other
        // cells in bottom-up manner using
        // the recursive solution
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++)
 
                // By uncommenting the last part the
                // code calculates the total possible paths
                // if the diagonal Movements are allowed
                count[i][j] = count[i - 1][j] + count[i][j - 1]; //+ count[i-1][j-1];
        }
        return count[m - 1][n - 1];
    }
 
    // Driver program to test above function
    public static void main(String args[])
    {
        System.out.println(numberOfPaths(3, 3));
    }
}
 
// This code is contributed by Sumit Ghosh

# Python program to count all possible paths
# from top left to bottom right
 
# 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):
    # Create a 2D table to store
    # results of subproblems
    # one-liner logic to take input for rows and columns
    # mat = [[int(input()) for x in range (C)] for y in range(R)]
     
    count = [[0 for x in range(n)] for y in range(m)]
   
    # Count of paths to reach any
    # cell in first column is 1
    for i in range(m):
        count[i][0] = 1;
   
    # Count of paths to reach any
    # cell in first column is 1
    for j in range(n):
        count[0][j] = 1;
   
    # Calculate count of paths for other
    # cells in bottom-up
    # manner using the recursive solution
    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]
 
# Driver program to test above function
m = 3
n = 3
print( numberOfPaths(m, n))
 
# This code is contributed by Aditi Sharma

// A C#  program to count all possible paths
// from top left to bottom right
using 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)
    {
        // Create a 2D table to store results
        // of subproblems
        int[, ] count = new int[m, n];
 
        // Count of paths to reach any cell in
        // first column is 1
        for (int i = 0; i < m; i++)
            count[i, 0] = 1;
 
        // Count of paths to reach any cell in
        // first column is 1
        for (int j = 0; j < n; j++)
            count[0, j] = 1;
 
        // Calculate count of paths for other
        // cells in bottom-up manner using
        // the recursive solution
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++)
 
                // By uncommenting the last part the
                // code calculates the total possible paths
                // if the diagonal Movements are allowed
                count[i, j] = count[i - 1, j] + count[i, j - 1]; //+ count[i-1][j-1];
        }
        return count[m - 1, n - 1];
    }
 
    // Driver program to test above function
    static public void Main()
    {
        Console.WriteLine(numberOfPaths(3, 3));
    }
}
 
// This code is contributed by akt_mit

<?php
// A PHP program to count all possible
// paths from top left to bottom right
 
// 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)
{
    // Create a 2D table to store
    // results of subproblems
    $count = array();
 
    // Count of paths to reach any cell
    // in first column is 1
    for ($i = 0; $i < $m; $i++)
        $count[$i][0] = 1;
 
    // Count of paths to reach any cell
    // in first column is 1
    for ($j = 0; $j < $n; $j++)
        $count[0][$j] = 1;
 
    // Calculate count of paths for other
    // cells in bottom-up manner using the
    // recursive solution
    for ($i = 1; $i < $m; $i++)
    {
        for ($j = 1; $j < $n; $j++)
 
            // By uncommenting the last part the
            // code calculated the total possible
            // paths if the diagonal Movements are allowed
            $count[$i][$j] = $count[$i - 1][$j] +
                             $count[$i][$j - 1]; //+ count[i-1][j-1];
    }
    return $count[$m - 1][$n - 1];
}
 
// Driver Code
echo numberOfPaths(3, 3);
 
// This code is contributed
// by Mukul Singh
?>

<script>
 
// A javascript program to count all possible paths
// from top left to bottom right
 
// 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)
{
    // Create a 2D table to store results
    // of subproblems
    var count = Array(m).fill(0).map(x => Array(n).fill(0));
 
    // Count of paths to reach any cell in
    // first column is 1
    for (i = 0; i < m; i++)
        count[i][0] = 1;
 
    // Count of paths to reach any cell in
    // first column is 1
    for (j = 0; j < n; j++)
        count[0][j] = 1;
 
    // Calculate count of paths for other
    // cells in bottom-up manner using
    // the recursive solution
    for (i = 1; i < m; i++) {
        for (j = 1; j < n; j++)
 
            // By uncommenting the last part the
            // code calculates the total possible paths
            // if the diagonal Movements are allowed
             
            //+ count[i-1][j-1];
            count[i][j] = count[i - 1][j] + count[i][j - 1];
    }
    return count[m - 1][n - 1];
}
 
// Driver program to test above function
document.write(numberOfPaths(3, 3));
 
// This code is contributed by 29AjayKumar
 
</script>

6

Complejidad de tiempo: O(M*N) – Debido a bucles for anidados. 
Espacio auxiliar: O(M*N) – Hemos utilizado un arreglo 2D de tamaño MxN.

Solución de Programación Dinámica Recursiva. La siguiente implementación se basa en el enfoque Top-Down.

// A C++ program to count all possible paths from
// top left to top bottom right using
// Recursive Dynamic Programming
#include <iostream>
#include <cstring>
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 n,int m,int DP[4][4]){
 
    if(n == 1 || m == 1)
        return DP[n][m] = 1;
     
    // Add the element in the DP table
    // If it is was not computed before
    if(DP[n][m] == 0)
        DP[n][m] = numberOfPaths(n - 1, m,DP) + numberOfPaths(n, m - 1,DP);
 
    return DP[n][m];
}
 
// Driver code
int main()
{
    // Create an empty 2D table
    int DP[4][4] = {0};
    memset(DP, 0, sizeof(DP));
 
    cout << numberOfPaths(3, 3,DP);
 
    return 0;
}
  // This code is contributed
  // by Gatea David

// Java program to count all possible paths from
// top left to top bottom right using
// Recursive Dynamic Programming
import 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 n, int m, int DP[][])
    {
 
        if (n == 1 || m == 1)
            return DP[n][m] = 1;
 
        // Add the element in the DP table
        // If it is was not computed before
        if (DP[n][m] == 0)
            DP[n][m] = numberOfPaths(n - 1, m, DP)
                       + numberOfPaths(n, m - 1, DP);
 
        return DP[n][m];
    }
 
    // Driver code
    public static void main(String args[])
    {
        // Create an empty 2D table
        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));
    }
}
 
// This code is contributed
// by Samim Hossain Mondal.

# Python program to count all possible paths from
# top left to top bottom right using
# Recursive Dynamic Programming
 
# 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(n, m, DP):
 
    if (n == 1 or m == 1):
        DP[n][m] = 1;
        return  1;
 
    # Add the element in the DP table
    # If it is was not computed before
    if (DP[n][m] == 0):
        DP[n][m] = numberOfPaths(n - 1, m, DP) + numberOfPaths(n, m - 1, DP);
 
    return DP[n][m];
 
# Driver code
if __name__ == '__main__':
   
    # Create an empty 2D table
    DP = [[0 for i in range(4)] for j in range(4)] ;
 
    print(numberOfPaths(3, 3, DP));
 
# This code is contributed by gauravrajput1

// C# program to count all possible paths from
// top left to top bottom right using
// Recursive Dynamic Programming
using System;
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 n, int m, int[, ] DP)
    {
 
        if (n == 1 || m == 1)
            return DP[n, m] = 1;
 
        // Add the element in the DP table
        // If it is was not computed before
        if (DP[n, m] == 0)
            DP[n, m] = numberOfPaths(n - 1, m, DP)
                       + numberOfPaths(n, m - 1, DP);
 
        return DP[n, m];
    }
 
    // Driver code
    public static void Main()
    {
        // Create an empty 2D table
        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));
    }
}
 
// This code is contributed
// by Samim Hossain Mondal.

<script>
// Javascript program to count all possible paths from
// top left to top bottom right using
// Recursive Dynamic Programming
 
// Create an empty 2D table
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;
    }
}
 
// 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(n, m, DP){
 
    if(n == 1 || m == 1)
        return DP[n][m] = 1;
     
    // Add the element in the DP table
    // If it is was not computed before
    if(DP[n][m] == 0)
        DP[n][m] = numberOfPaths(n - 1, m,DP) + numberOfPaths(n, m - 1,DP);
 
    return DP[n][m];
}
 
// Driver code
 
document.write(numberOfPaths(3, 3,DP));
 
// This code is contributed
// by Samim Hossain Mondal.
 
</script>

6

La complejidad temporal de las 2 soluciones de programación dinámica anteriores es O(mn). 
La complejidad espacial de las 2 soluciones anteriores es O(mn), que es un espacio de pila.
Optimización del espacio de la solución DP. 

La solución anterior es más intuitiva, pero también podemos reducir el espacio en O(n); donde n es el tamaño de la columna. 
Implementación:

#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)
{
    // Create a 1D array to store results of subproblems
    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];
}
 
// Driver code
int main()
{
    cout << numberOfPaths(3, 3);
}
 
// This code is contributed by mohit kumar 29

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)
    {
        // Create a 1D array to store results of subproblems
        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];
    }
 
    // Driver program to test above function
    public static void main(String args[])
    {
        System.out.println(numberOfPaths(3, 3));
    }
}

# 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(p, q):
     
    # Create a 1D array to store
    # results of subproblems
    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]
 
# Driver Code
print(numberOfPaths(3, 3))
 
# This code is contributed
# by Ankit Yadav

using System;
 
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)
    {
        // Create a 1D array to store
        // results of subproblems
        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];
    }
 
    // Driver Code
    public static void Main()
    {
        Console.Write(numberOfPaths(3, 3));
    }
}
 
// This code is contributed
// by ChitraNayal

<?php
// 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)
{
    // Create a 1D array to store
    // results of subproblems
    $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];
}
 
// Driver Code
echo numberOfPaths(3, 3);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
 
// 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)
{
    // Create a 1D array to store results of subproblems
    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];
}
 
// Driver program to test above function
document.write(numberOfPaths(3, 3));
 
// This code contributed by Princi Singh
 
</script>

6

Tiempo Complejidad: O(m*n)
Espacio Auxiliar: O(n)

Este código es aportado por Vivek Singh

Tenga en cuenta que el recuento también se puede calcular mediante la fórmula (m-1 + n-1)!/(m-1)!(n-1)!. 

Otro enfoque: (Usando la combinatoria) En este enfoque, ¡tenemos que calcular ^m+n-2 C _n-1 aquí, que será (m+n-2)! / (n-1)! (m-1)! 

Ahora, veamos cómo esta fórmula da la respuesta correcta (Referencia 1) (Referencia 2) lea la referencia 1 y la referencia 2 para una mejor comprensión

m = número de filas, n = número de columnas

Número total de movimientos en los que tenemos que bajar para llegar a la última fila = m – 1 (m filas, ya que estamos comenzando desde (1, 1) que no está incluido)

Número total de movimientos en los que tenemos que movernos hacia la derecha para llegar a la última columna = n – 1 (columna n, ya que estamos comenzando desde (1, 1) que no está incluido)

Movimientos hacia abajo = (m – 1)
Movimientos hacia la derecha = (n – 1)

Movimientos totales = Movimientos hacia abajo + Movimientos hacia la derecha = (m – 1) + (n – 1) 

Ahora piense en los movimientos como una string de caracteres ‘R’ y ‘D’ donde ‘R’ en cualquier i-ésimo índice nos dirá que nos movemos ‘Derecha’ y ‘D’ nos dirá que nos movamos ‘Abajo’

Ahora piense en cuántas strings únicas (movimientos) podemos hacer donde en total debería haber (n – 1 + m – 1) caracteres y debería haber (m – 1) carácter ‘D’ y (n – 1) ‘R ‘ ¿personaje? 

La elección de posiciones de (n – 1) caracteres ‘R’ da como resultado la elección automática de (m – 1) posiciones de caracteres ‘D’ 

Calcular ⁿ C _r 
Número de formas de elegir posiciones para (n – 1) carácter ‘R’ = ^{Posiciones totales} C _{n – 1} = ^{Posiciones totales} C _{m – 1} = (n – 1 + m – 1) !=  

Otra forma de pensar en este problema: cuente el número de formas de hacer una string binaria de N dígitos (string con 0 y 1 solamente) con ceros ‘X’ y unos ‘Y’ (aquí hemos reemplazado ‘R’ con ‘0’ o ‘1’ y ‘D’ con ‘1’ o ‘0’ respectivamente, lo que más le convenga) 

// A C++ program to count all possible paths from
// top left to top bottom using combinatorics
 
#include <iostream>
using namespace std;
 
int numberOfPaths(int m, int n)
{
    // We have to calculate m+n-2 C n-1 here
    // which will be (m+n-2)! / (n-1)! (m-1)!
    int path = 1;
    for (int i = n; i < (m + n - 1); i++) {
        path *= i;
        path /= (i - n + 1);
    }
    return path;
}
 
// Driver code
int main()
{
    cout << numberOfPaths(3, 3);
    return 0;
}
 
// This code is suggested by Kartik Sapra

// Java program to count all possible paths from
// top left to top bottom using combinatorics
class GFG {
 
    static int numberOfPaths(int m, int n)
    {
        // We have to calculate m+n-2 C n-1 here
        // which will be (m+n-2)! / (n-1)! (m-1)!
        int path = 1;
        for (int i = n; i < (m + n - 1); i++) {
            path *= i;
            path /= (i - n + 1);
        }
        return path;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        System.out.println(numberOfPaths(3, 3));
    }
}
 
// This code is contributed by Code_Mech.

# Python3 program to count all possible
# paths from top left to top bottom
# using combinatorics
def numberOfPaths(m, n) :
    path = 1
    # We have to calculate m + n-2 C n-1 here
    # which will be (m + n-2)! / (n-1)! (m-1)! path = 1;
    for i in range(n, (m + n - 1)):
        path *= i;
        path //= (i - n + 1);
     
    return path;
 
# Driver code
print(numberOfPaths(3, 3));
 
# This code is contributed
# by Akanksha Rai

// C# program to count all possible paths from
// top left to top bottom using combinatorics
using System;
 
class GFG {
 
    static int numberOfPaths(int m, int n)
    {
        // We have to calculate m+n-2 C n-1 here
        // which will be (m+n-2)! / (n-1)! (m-1)!
        int path = 1;
        for (int i = n; i < (m + n - 1); i++) {
            path *= i;
            path /= (i - n + 1);
        }
        return path;
    }
 
    // Driver code
    public static void Main()
    {
        Console.WriteLine(numberOfPaths(3, 3));
    }
}
 
// This code is contributed by Code_Mech.

<?php
 
// PHP program to count all possible paths from
// top left to top bottom using combinatorics
function numberOfPaths($m, $n)
{
    // We have to calculate m+n-2 C n-1 here
    // which will be (m+n-2)! / (n-1)! (m-1)!
    $path = 1;
    for ($i = $n; $i < ($m + $n - 1); $i++)
    {
        $path *= $i;
        $path /= ($i - $n + 1);
    }
    return $path;
}
 
// Driver code
{
    echo(numberOfPaths(3, 3));
}
 
// This code is contributed by Code_Mech.

<script>
 
// javascript program to count all possible paths from
// top left to top bottom using combinatorics  
function numberOfPaths(m , n)
    {
        // We have to calculate m+n-2 C n-1 here
        // which will be (m+n-2)! / (n-1)! (m-1)!
        var path = 1;
        for (i = n; i < (m + n - 1); i++) {
            path *= i;
            path = parseInt(path/(i - n + 1));
        }
        return path;
    }
 
// Driver code
document.write(numberOfPaths(3, 3));
 
// This code contributed by Princi Singh
</script>

6

Complejidad temporal: O(m+n)

Espacio Auxiliar: O(1)

Este artículo es una contribución de Hariprasad NG . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.