Cuenta caminos desde un punto hasta llegar al Origen

Está parado en un punto (n, m) y quiere ir al origen (0, 0) dando pasos hacia la izquierda o hacia abajo, es decir, desde cada punto puede moverse en (n-1, m) o ( n, m-1) . Encuentre el número de caminos desde el punto hasta el origen.

Ejemplos: 

Input : 3 6
Output : Number of Paths 84

Input : 3 0
Output : Number of Paths 1

Como estamos restringidos a movernos solo hacia abajo y hacia la izquierda, ejecutaríamos un bucle recursivo para cada una de las combinaciones de los 
pasos que se pueden tomar.

// Recursive function to count number of paths
countPaths(n, m)
{
    // If we reach bottom or top left, we are
    // have only one way to reach (0, 0)
    if (n==0 || m==0)
        return 1;

    // Else count sum of both ways
    return (countPaths(n-1, m) + countPaths(n, m-1));
} 

A continuación se muestra la implementación de los pasos anteriores. 

// C++ program to count total number of
// paths from a point to origin
#include<bits/stdc++.h>
using namespace std;
 
// Recursive function to count number of paths
int countPaths(int n, int m)
{
    // If we reach bottom or top left, we are
    // have only one way to reach (0, 0)
    if (n==0 || m==0)
        return 1;
 
    // Else count sum of both ways
    return (countPaths(n-1, m) + countPaths(n, m-1));
}
 
// Driver Code
int main()
{
    int n = 3, m = 2;
    cout << " Number of Paths " << countPaths(n, m);
    return 0;
}

// Java program to count total number of
// paths from a point to origin
import java.io.*;
 
class GFG {
     
    // Recursive function to count number of paths
    static int countPaths(int n, int m)
    {
        // If we reach bottom or top left, we are
        // have only one way to reach (0, 0)
        if (n == 0 || m == 0)
            return 1;
     
        // Else count sum of both ways
        return (countPaths(n - 1, m) + countPaths(n, m - 1));
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int n = 3, m = 2;
        System.out.println (" Number of Paths "
                            + countPaths(n, m));
         
    }
}
 
// This code is contributed by vt_m

# Python3 program to count
# total number of
# paths from a point to origin
# Recursive function to
# count number of paths
def countPaths(n,m):
 
    # If we reach bottom
    # or top left, we are
    # have only one way to reach (0, 0)
    if (n==0 or m==0):
        return 1
  
    # Else count sum of both ways
    return (countPaths(n-1, m) + countPaths(n, m-1))
 
# Driver Code
n = 3
m = 2
print(" Number of Paths ", countPaths(n, m))
 
# This code is contributed
# by Azkia Anam.

// C# program to count total number of
// paths from a point to origin
using System;
         
public class GFG {
     
    // Recursive function to count number
    // of paths
    static int countPaths(int n, int m)
    {
         
        // If we reach bottom or top left,
        // we are have only one way to
        // reach (0, 0)
        if (n == 0 || m == 0)
            return 1;
     
        // Else count sum of both ways
        return (countPaths(n - 1, m)
                 + countPaths(n, m - 1));
    }
     
    // Driver Code
    public static void Main ()
    {
        int n = 3, m = 2;
         
        Console.WriteLine (" Number of"
         + " Paths " + countPaths(n, m));
         
    }
}
 
// This code is contributed by Sam007.

<?php
// PHP program to count total number
// of paths from a point to origin
 
// Recursive function to
// count number of paths
function countPaths($n, $m)
{
     
    // If we reach bottom or
    // top left, we are
    // have only one way to
    // reach (0, 0)
    if ($n == 0 || $m == 0)
        return 1;
 
    // Else count sum of both ways
    return (countPaths($n - 1, $m) +
            countPaths($n, $m - 1));
}
 
    // Driver Code
    $n = 3;
    $m = 2;
    echo " Number of Paths "
      , countPaths($n, $m);
 
// This code is contributed by aj_36
?>

<script>
 
// Javascript program to count total number of
// paths from a point to origin
 
    // Recursive function to count number of paths
    function countPaths( n , m) {
        // If we reach bottom or top left, we are
        // have only one way to reach (0, 0)
        if (n == 0 || m == 0)
            return 1;
 
        // Else count sum of both ways
        return (countPaths(n - 1, m) + countPaths(n, m - 1));
    }
 
    // Driver Code
      
        let n = 3, m = 2;
        document.write(" Number of Paths " + countPaths(n, m));
 
// This code is contributed by shikhasingrajput
 
</script>

 Number of Paths 10

Podemos usar Programación Dinámica ya que hay subproblemas superpuestos. Podemos dibujar un árbol de recursión para ver problemas superpuestos. Por ejemplo, en el caso de countPaths(4, 4), calculamos countPaths(3, 3) varias veces.

// C++ program to count total number of
// paths from a point to origin
#include<bits/stdc++.h>
using namespace std;
 
// DP based function to count number of paths
int countPaths(int n, int m)
{
    int dp[n+1][m+1];
 
    // Fill entries in bottommost row and leftmost
    // columns
    for (int i=0; i<=n; i++)
      dp[i][0] = 1;
    for (int i=0; i<=m; i++)
      dp[0][i] = 1;
 
    // Fill DP in bottom up manner
    for (int i=1; i<=n; i++)
       for (int j=1; j<=m; j++)
          dp[i][j] = dp[i-1][j] + dp[i][j-1];
 
    return dp[n][m];
}
 
// Driver Code
int main()
{
    int n = 3, m = 2;
    cout << " Number of Paths " << countPaths(n, m);
    return 0;
}

// Java program to count total number of
// paths from a point to origin
import java.io.*;
 
class GFG {
     
    // DP based function to count number of paths
    static int countPaths(int n, int m)
    {
        int dp[][] = new int[n + 1][m + 1];
     
        // Fill entries in bottommost row and leftmost
        // columns
        for (int i = 0; i <= n; i++)
            dp[i][0] = 1;
        for (int i = 0; i <= m; i++)
            dp[0][i] = 1;
     
        // Fill DP in bottom up manner
        for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
     
        return dp[n][m];
    }
     
    // Driver Code
    public static void main (String[] args) {
        int n = 3, m = 2;
        System.out.println(" Number of Paths "
                           + countPaths(n, m));
         
    }
}
 
// This code is contributed by vt_m

# Python3 program to count total
# number of paths from a point to origin
 
# Recursive function to count
# number of paths
def countPaths(n, m):
 
    # If we reach bottom or top
    # left, we are have only one
    # way to reach (0, 0)
    if (n == 0 or m == 0):
        return 1
 
    # Else count sum of both ways
    return (countPaths(n - 1, m) +
            countPaths(n, m - 1))
 
# Driver Code
n = 3
m = 2
print("Number of Paths",
       countPaths(n, m))
 
# This code is contributed by ash264

// C# program to count total number of
// paths from a point to origin
using System;
         
public class GFG {
     
    // DP based function to count number
    // of paths
    static int countPaths(int n, int m)
    {
        int [,]dp = new int[n + 1,m + 1];
     
        // Fill entries in bottommost row
        // and leftmost columns
        for (int i = 0; i <= n; i++)
            dp[i,0] = 1;
        for (int i = 0; i <= m; i++)
            dp[0,i] = 1;
     
        // Fill DP in bottom up manner
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i,j] = dp[i - 1,j]
                         + dp[i,j - 1];
         
        return dp[n,m];
    }
     
    // Driver Code
    public static void Main ()
    {
        int n = 3, m = 2;
         
        Console.WriteLine(" Number of"
        + " Paths " + countPaths(n, m));
         
    }
}
 
// This code is contributed by Sam007.

<?php
// PHP program to count total number of
// paths from a point to origin
 
// DP based function to
// count number of paths
function countPaths($n, $m)
{
     
    //$dp[$n+1][$m+1];
    // Fill entries in bottommost
    // row and leftmost columns
    for ($i = 0; $i <= $n; $i++)
        $dp[$i][0] = 1;
         
    for ($i = 0; $i <= $m; $i++)
        $dp[0][$i] = 1;
 
    // Fill DP in bottom up manner
    for ($i = 1; $i <= $n; $i++)
    for ($j = 1; $j <= $m; $j++)
        $dp[$i][$j] = $dp[$i - 1][$j] +
                      $dp[$i][$j - 1];
 
    return $dp[$n][$m];
}
 
    // Driver Code
    $n = 3;
    $m = 2;
    echo " Number of Paths " , countPaths($n, $m);
 
// This code is contributed by m_kit
?>

<script>
// javascript program to count total number of
// paths from a point to origin
    
// DP based function to count number of paths
function countPaths(n , m)
{
    var dp = Array(n+1).fill(0).map(x => Array(m+1).fill(0));
 
    // Fill entries in bottommost row and leftmost
    // columns
    for (i = 0; i <= n; i++)
        dp[i][0] = 1;
    for (i = 0; i <= m; i++)
        dp[0][i] = 1;
 
    // Fill DP in bottom up manner
    for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++)
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
 
    return dp[n][m];
}
     
// Driver Code
var n = 3, m = 2;
document.write(" Number of Paths "
                   + countPaths(n, m)); 
                    
// This code is contributed by Amit Katiyar
</script>

 Number of Paths 10

Otro enfoque:

Usando el método del triángulo de Pascal, también resolvemos el problema calculando el valor de ^n+m C _n . Se puede observar como un patrón cuando aumentas el valor de m manteniendo constante el valor de n .
A continuación se muestra la implementación del enfoque anterior:

Implementación:

// C++ Program for above approach
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
// Function to find
// binomial Coefficient
int binomialCoeff(int n, int k)
{
    int C[k+1];
    memset(C, 0, sizeof(C));
    C[0] = 1;
   
    // Constructing Pascal's Triangle
    for (int i = 1; i <= n; i++)
    {
        for (int j = min(i, k); j > 0; j--)
            C[j] = C[j] + C[j-1];
    }
    return C[k];
}
 
//Driver Code
int main()
{
    int n=3, m=2;
    cout<<"Number of Paths: "<<
                binomialCoeff(n+m,n)<<endl;
    return 0;
}
 
//Contributed by Vismay_7

// Java Program for above approach
import java.io.*;
import java.util.*;
 
class GFG
{
    static int min(int a,int b)
    {
        return a<b?a:b;
    }
   
    // Function for binomial
    // Coefficient
    static int binomialCoeff(int n, int k)
    {
        int C[] = new int[k + 1];
        C[0] = 1; 
         
        //Constructing Pascal's Triangle
        for (int i = 1; i <= n; i++)
        {
            for (int j = min(i,k); j > 0; j--)
                C[j] = C[j] + C[j-1];
        }
        return C[k];
    }
   
    // Driver Code
    public static void main (String[] args)
    {
        int n=3,m=2;
        System.out.println("Number of Paths: " +
                           binomialCoeff(n+m,n));
    }
}
//Contributed by Vismay_7

# Python3 program for above approach
def binomialCoeff(n,k):
     
    C = [0]*(k+1)
    C[0] = 1
     
    # Computing Pascal's Triangle
    for i in range(1, n + 1):
         
        j = min(i ,k)
        while (j > 0):
            C[j] = C[j] + C[j-1]
            j -= 1
   
    return C[k]
   
# Driver Code
n=3
m=2
print("Number of Paths:",binomialCoeff(n+m,n))
 
# Contributed by Vismay_7

// C# program for above approach
using System;
 
class GFG{
     
// Function to find
// binomial Coefficient
static int binomialCoeff(int n, int k)
{
    int[] C = new int[k + 1];
    C[0] = 1;
    
    // Constructing Pascal's Triangle
    for(int i = 1; i <= n; i++)
    {
        for(int j = Math.Min(i, k); j > 0; j--)
            C[j] = C[j] + C[j - 1];
    }
    return C[k];
}
 
// Driver code
static void Main()
{
    int n = 3, m = 2;
     
    Console.WriteLine("Number of Paths: " +
                      binomialCoeff(n + m, n));
}
}
 
// This code is contributed by divyesh072019

<script>
// javascript Program for above approach
    function min(a , b)
    {
        return a < b ? a : b;
    }
 
    // Function for binomial
    // Coefficient
    function binomialCoeff(n , k)
    {
        var C = Array(k + 1).fill(0);
        C[0] = 1;
 
        // Constructing Pascal's Triangle
        for (i = 1; i <= n; i++)
        {
            for (j = min(i, k); j > 0; j--)
                C[j] = C[j] + C[j - 1];
        }
        return C[k];
    }
 
    // Driver Code
    var n = 3, m = 2;
    document.write("Number of Paths: " + binomialCoeff(n + m, n));
 
// This code is contributed by Amit Katiyar 
</script>

Number of Paths: 10

Nikhil Rawat contribuye con este artículo . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando write.geeksforgeeks.org o enviar su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.