Programa C# para Contar formas de llegar a la escalera número n

Hay n escaleras, una persona parada en la parte inferior quiere llegar a la cima. La persona puede subir 1 o 2 escalones a la vez. Cuente el número de formas en que la persona puede llegar a la cima. Considere el ejemplo que se muestra en el diagrama. El valor de n es 3. Hay 3 formas de llegar a la cima. El diagrama está tomado de los rompecabezas de Fibonacci más fáciles. 

// C# program to count the
// number of ways to reach
// n'th stair
using System;
 
class GFG {
    // A simple recursive
    // program to find n'th
    // fibonacci number
    static int fib(int n)
    {
        if (n <= 1)
            return n;
        return fib(n - 1) + fib(n - 2);
    }
 
    // Returns number of ways
    // to reach s'th stair
    static int countWays(int s)
    {
        return fib(s + 1);
    }
 
    // Driver Code
    static public void Main()
    {
        int s = 4;
        Console.WriteLine("Number of ways = " + countWays(s));
    }
}
 
// This code is contributed
// by akt_mit

Number of ways = 5

La complejidad temporal de la implementación anterior es exponencial (proporción áurea elevada a la potencia n). Se puede optimizar para que funcione en tiempo O (Logn) utilizando las optimizaciones de funciones de Fibonacci discutidas anteriormente . 

// C# program to Count ways to reach
// the n’th stair
using System;
 
class GFG {
 
    // A recursive function used by
    // countWays
    static int countWaysUtil(int n, int m)
    {
        if (n <= 1)
            return n;
        int res = 0;
 
        for (int i = 1; i <= m && i <= n; i++)
            res += countWaysUtil(n - i, m);
        return res;
    }
 
    // Returns number of ways to reach
    // s'th stair
    static int countWays(int s, int m)
    {
        return countWaysUtil(s + 1, m);
    }
 
    /* Driver program to test above function */
    public static void Main()
    {
        int s = 4, m = 2;
        Console.Write("Number of ways = "
                      + countWays(s, m));
    }
}
 
// This code is contributed by nitin mittal.

Number of ways = 5

Complejidad temporal: O(2 ⁿ )
Espacio auxiliar: O(n)

// C# program to count number
// of ways to reach n't stair when
// a person can climb 1, 2, ..m
// stairs at a time
using System;
class GFG {
 
    // A recursive function
    // used by countWays
    static int countWaysUtil(int n, int m)
    {
        int[] res = new int[n];
        res[0] = 1;
        res[1] = 1;
        for (int i = 2; i < n; i++) {
            res[i] = 0;
            for (int j = 1; j <= m && j <= i; j++)
                res[i] += res[i - j];
        }
        return res[n - 1];
    }
 
    // Returns number of ways
    // to reach s'th stair
    static int countWays(int s, int m)
    {
        return countWaysUtil(s + 1, m);
    }
 
    // Driver Code
    public static void Main()
    {
        int s = 4, m = 2;
        Console.WriteLine("Number of ways = " + countWays(s, m));
    }
}
 
// This code is contributed by anuj_67.

Number of ways = 5

Complejidad del tiempo : O(m*n)

Espacio Auxiliar : O(n)

Consulte el artículo completo sobre las formas de contar para llegar al escalón n para obtener más detalles.