camino dick

Considere una cuadrícula anxn con índices de la esquina superior izquierda como (0, 0). Dyck Path es una escalera desde la parte inferior izquierda, es decir, (n-1, 0) hasta la parte superior derecha, es decir, (0, n-1) que se encuentra sobre las celdas diagonales (o celdas en línea desde la parte inferior izquierda hasta la parte superior derecha) .
La tarea es contar el número de Dyck Paths desde (n-1, 0) hasta (0, n-1).
Ejemplos: 

Input : n = 1
Output : 1

Input : n = 2
Output : 2

Input : n = 3
Output : 5

Input : n = 4
Output : 14

El número de caminos de Dyck de (n-1, 0) a (0, n-1) puede ser dado por el número catalán C(n).

 

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

A continuación se muestran las implementaciones para encontrar el recuento de Dyck Paths (o n’ésimo número catalán).
 

// C++ program to count
// number of Dyck Paths
#include<iostream>
using namespace std;
 
// Returns count Dyck
// paths in n x n grid
int countDyckPaths(unsigned int n)
{
    // Compute value of 2nCn
    int res = 1;
    for (int i = 0; i < n; ++i)
    {
        res *= (2 * n - i);
        res /= (i + 1);
    }
 
    // return 2nCn/(n+1)
    return res / (n+1);
}
 
// Driver Code
int main()
{
    int n = 4;
    cout << "Number of Dyck Paths is "
         << countDyckPaths(n);
    return 0;
}

// Java program to count
// number of Dyck Paths
class GFG
{
    // Returns count Dyck
    // paths in n x n grid
    public static int countDyckPaths(int n)
    {
        // Compute value of 2nCn
        int res = 1;
        for (int i = 0; i < n; ++i)
        {
            res *= (2 * n - i);
            res /= (i + 1);
        }
 
        // return 2nCn/(n+1)
        return res / (n + 1);
    }
 
    // Driver code
    public static void main(String args[])
    {
        int n = 4;
        System.out.println("Number of Dyck Paths is " +
                                    countDyckPaths(n));
    }
}

# Python3 program to count
# number of Dyck Paths
 
# Returns count Dyck
# paths in n x n grid
def countDyckPaths(n):
     
    # Compute value of 2nCn
    res = 1
    for i in range(0, n):
        res *= (2 * n - i)
        res /= (i + 1)
 
    # return 2nCn/(n+1)
    return res / (n+1)
 
# Driver Code
n = 4
print("Number of Dyck Paths is ",
    str(int(countDyckPaths(n))))
 
# This code is contributed by
# Prasad Kshirsagar

// C# program to count
// number of Dyck Paths
using System;
 
class GFG {
     
    // Returns count Dyck
    // paths in n x n grid
    static int countDyckPaths(int n)
    {
         
        // Compute value of 2nCn
        int res = 1;
        for (int i = 0; i < n; ++i)
        {
            res *= (2 * n - i);
            res /= (i + 1);
        }
 
        // return 2nCn/(n+1)
        return res / (n + 1);
    }
 
    // Driver code
    public static void Main()
    {
        int n = 4;
        Console.WriteLine("Number of "
                  + "Dyck Paths is " +
                   countDyckPaths(n));
    }
}
 
// This code is contributed by anuj_67.

<?php
// PHP program to count
// number of Dyck Paths
 
// Returns count Dyck
// paths in n x n grid
function countDyckPaths( $n)
{
    // Compute value of 2nCn
    $res = 1;
    for ( $i = 0; $i < $n; ++$i)
    {
        $res *= (2 * $n - $i);
        $res /= ($i + 1);
    }
 
    // return 2nCn/(n+1)
    return $res / ($n + 1);
}
 
// Driver Code
$n = 4;
echo "Number of Dyck Paths is " ,
              countDyckPaths($n);
 
// This code is contributed by anuj_67.
?>

<script>
 
// JavaScript program to count
// number of Dyck Paths
 
    // Returns count Dyck
    // paths in n x n grid
    function countDyckPaths(n)
    {
     
        // Compute value of 2nCn
        let res = 1;
        for (let i = 0; i < n; ++i)
        {
            res *= (2 * n - i);
            res /= (i + 1);
        }
   
        // return 2nCn/(n+1)
        return res / (n + 1);
    }
 
// Driver Code
 
        let n = 4;
        document.write("Number of Dyck Paths is " +
                                    countDyckPaths(n));
     
    // This code is contributed by target_2.
</script>

Producción : 
 

Number of Dyck Paths is 14

Ejercicio : 
 

1. Encuentre el número de secuencias de 1 y -1 tal que cada secuencia siga las siguientes restricciones: 
   a) La longitud de una secuencia es 2n 
   b) Hay igual número de 1 y -1, es decir, n 1, n -1 
   c) Suma de El prefijo de cada secuencia es mayor o igual a 0. Por ejemplo, 1, -1, 1, -1 y 1, 1, -1, -1 son válidos, pero -1, -1, 1, 1 no es válido .
2. Número de caminos de longitud m + n desde (m-1, 0) hasta (0, n-1) que están restringidos a los pasos este y norte.

Este artículo es una contribución de Aditya Chatterjee . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.