Suba la escalera n-ésima con todos los saltos del 1 al n permitidos (tres enfoques diferentes)

Un mono está parado debajo de una escalera que tiene N escalones. Teniendo en cuenta que puede dar un salto de 1 a N pasos a la vez, ¿calcula de cuántas maneras puede llegar a la parte superior de la escalera?

Ejemplos: 

Input : 2
Output : 2
It can either take (1, 1) or (2) to
reach the top. So, total 2 ways

Input : 3
Output : 4
Possibilities : (1, 1, 1), (1, 2), (2, 1),
(3). So, total 4 ways 

Hay 3 maneras diferentes de pensar en el problema. 

1. En todas las soluciones posibles, el mono pisa un paso o se puede omitir. Entonces, utilizando el principio fundamental de conteo , el primer paso tiene 2 formas de participar, y para cada una de estas, el segundo paso también tiene 2 formas, y así sucesivamente. pero el último escalón siempre hay que pisarlo.

  2 x 2 x 2 x .... x 2(N-1 th step) x 1(Nth step) 
  = 2(N-1) different ways. 

1. Definamos una función F(n) para el caso de uso. F(n) denota todas las formas posibles de llegar desde la parte inferior hasta la parte superior de una escalera que tiene N escalones, donde el salto mínimo es 1 escalón y el salto máximo es N escalón. Ahora, para el mono, el primer movimiento que puede hacer es posible de N maneras diferentes (1 paso, 2 pasos, 3 pasos… N pasos). Si da el primer salto como 1 paso, le quedarán N-1 pasos más para conquistar, lo que se puede lograr de formas F(N-1). Y si da el primer salto como 2 pasos, tendrá N-2 pasos más para cubrir, lo que se puede lograr de formas F(N-2). Poner juntos,

F(N) = F(N-1) + F(N-2) + F(N-3) + ... + 
                      F(2) + F(1) + F(0) 
Now, 
F(0) = 1
F(1) = 1
F(2) = 2
F(3) = 4

Hence,
F(N) = 1 + 1 + 2 + 4 + ... + F(n-1)
     = 1 + 2^0 + 2^1 + 2^2 + ... + 2^(n-2)
     = 1 + [2^(n-1) - 1]

// C++ program to count total number of ways
// to reach n-th stair with all jumps allowed
#include <iostream>
 
int calculateLeaps(int n)
{
    if (n == 0 || n == 1) {
        return 1;
    }
    else {
        int leaps = 0;
        for (int i = 0; i < n; i++)
            leaps += calculateLeaps(i);
        return leaps;
    }
}
 
// Driver code
int main()
{
    int calculateLeaps(int);
    std::cout << calculateLeaps(4) << std::endl;
    return 0;
}

// Java program to count total number of ways
// to reach n-th stair with all jumps allowed
class GFG {
    static int calculateLeaps(int n)
    {
        if (n == 0 || n == 1) {
            return 1;
        }
        else {
            int leaps = 0;
            for (int i = 0; i < n; i++)
                leaps += calculateLeaps(i);
            return leaps;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        System.out.println(calculateLeaps(4));
    }
}
// This code is contributed by Anant Agarwal.

# Python program to count
# total number of ways
# to reach n-th stair with
# all jumps allowed
 
def calculateLeaps(n):
    if n == 0 or n == 1:
        return 1;
    else:
        leaps = 0;
        for i in range(0,n):
            leaps = leaps + calculateLeaps(i);
        return leaps;
 
# Driver code
print(calculateLeaps(4));
 
# This code is contributed by mits

// C# program to count total number of ways
// to reach n-th stair with all jumps allowed
using System;
 
class GFG {
 
    // Function to calculate leaps
    static int calculateLeaps(int n)
    {
        if (n == 0 || n == 1) {
            return 1;
        }
        else {
            int leaps = 0;
            for (int i = 0; i < n; i++)
                leaps += calculateLeaps(i);
            return leaps;
        }
    }
 
    // Driver code
    public static void Main()
    {
        Console.WriteLine(calculateLeaps(4));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to count total
// number of ways to reach
// n-th stair with all
// jumps allowed
 
// function return the
// number of ways
function calculateLeaps($n)
{
    if ($n == 0 || $n == 1)
    {
        return 1;
    }
    else
    {
        $leaps = 0;
        for ($i = 0; $i < $n; $i++)
            $leaps += calculateLeaps($i);
        return $leaps;
    }
}
 
    // Driver Code
    echo calculateLeaps(4), "\n";
 
// This code is contributed by ajit
?>

<script>
    // Javascript program to count total number of ways
    // to reach n-th stair with all jumps allowed
     
    // Function to calculate leaps
    function calculateLeaps(n)
    {
        if (n == 0 || n == 1) {
            return 1;
        }
        else {
            let leaps = 0;
            for (let i = 0; i < n; i++)
                leaps += calculateLeaps(i);
            return leaps;
        }
    }
     
    document.write(calculateLeaps(4));
     
</script>

1. Producción:

8

Complejidad de tiempo : O(2 ⁿ )

Espacio auxiliar : O (n) debido al espacio de pila recursivo

2. La solución anterior se puede mejorar utilizando la programación dinámica (enfoque ascendente)

                              Leaps(3)
                         3/      2|         1\
                     Leaps(0)   Leaps(1)            Leaps(2)
                    /   |   \                   3/       2|     1\
          Leaps(-3) Leaps(-2)  Leaps(-1)   Lepas(-1) Leaps(0) Leaps(1)

// C++ program to count total number of ways
// to reach n-th stair with all jumps allowed
 
#include <iostream>
using namespace std;
 
int calculateLeaps(int n, int dp[]){
    if(n == 0){
        return 1 ;
    }else if(n < 0){
        return 0 ;
    }
     
    if(dp[n] != 0 ){
       return dp[n] ;
    }
 
    int count = 0;
    for(int i = 0 ; i < n ; i++ ){
        count += calculateLeaps(i, dp)  ;
    }
     
    dp[n] = count ;
    return count ;
     
}
int main() {
    int n = 4 ;
     
    int dp[n+1] = {0} ;
     
    cout<<calculateLeaps(n,dp) ;
 
    return 0;
   
}

// Java program to count total number of ways
// to reach n-th stair with all jumps allowed
import java.io.*;
 
class GFG
{
  public static int calculateLeaps(int n, int dp[])
  {
    if(n == 0)
    {
      return 1 ;
    }
    else if(n < 0)
    {
      return 0 ;
    }
 
    if(dp[n] != 0)
    {
      return dp[n] ;
    }
 
    int count = 0;
    for(int i = 0 ; i < n ; i++)
    {
      count += calculateLeaps(i, dp);
    }
 
    dp[n] = count;
    return count;
  }
 
  // Driver Code
  public static void main (String[] args)
  {
    int n = 4;
    int dp[] = new int[n+1];
    System.out.println(calculateLeaps(n,dp));
  }
}
 
// This code is contributed by kothavvsaakash

# Python program to count total number of ways
# to reach n-th stair with all jumps allowed
def calculateLeaps(n, dp):
 
    if(n == 0):
        return 1
    elif(n < 0):
        return 0
     
    if(dp[n] != 0 ):
       return dp[n]
 
    count = 0
    for i in range(n):
        count += calculateLeaps(i, dp)
     
    dp[n] = count
    return count
     
# driver code
n = 4
dp = [0]*(n+1)
print(calculateLeaps(n,dp))
 
# This code is contributed by shinjanpatra

// C# program to count total number of ways
// to reach n-th stair with all jumps allowed
using System;
 
class GFG
{
  public static int calculateLeaps(int n, int[] dp)
  {
    if(n == 0)
    {
      return 1 ;
    }
    else if(n < 0)
    {
      return 0 ;
    }
 
    if(dp[n] != 0)
    {
      return dp[n] ;
    }
 
    int count = 0;
    for(int i = 0 ; i < n ; i++)
    {
      count += calculateLeaps(i, dp);
    }
 
    dp[n] = count;
    return count;
  }
 
  // Driver Code
  public static void Main (string[] args)
  {
    int n = 4;
    int[] dp = new int[n+1];
    Console.WriteLine(calculateLeaps(n,dp));
  }
}
 
// This code is contributed by phasing17

<script>
 
// JavaScript program to count total number of ways
// to reach n-th stair with all jumps allowed
function calculateLeaps(n, dp){
    if(n == 0){
        return 1
    }else if(n < 0){
        return 0
    }
     
    if(dp[n] != 0 ){
       return dp[n]
    }
 
    let count = 0
    for(let i = 0 ; i < n ; i++ ){
        count += calculateLeaps(i, dp)
    }
     
    dp[n] = count
    return count
     
}
 
// driver code
let n = 4
let dp = new Array(n+1).fill(0)
document.write(calculateLeaps(n,dp))
 
// This code is contributed by shinjanpatra
 
</script>

Complejidad de tiempo: O(n) // estados máximos diferentes

Espacio auxiliar: O(n) + O(n) -> O(n) // espacio de pila auxiliar + tamaño de array dp

3. Dividamos este problema en pequeños subproblemas. El mono tiene que pisar el último escalón, los primeros N-1 pasos son opcionales. El mono puede pisar 0 escalones antes de llegar al escalón superior, que es el mayor salto hacia la cima. O puede decidir pisar solo una vez en el medio, lo que se puede lograr de n-1 formas [ ^(N-1) C ₁ ]. Y así sucesivamente, puede pisar sólo 2 escalones antes de llegar a la cima en ^(N-1) C ₂ vías. Juntando..
F(N) = ^(N-1) C ₀ + ^(N-1) C ₁ + ^(N-1) C ₂ + … + ^(N-1) C _(N-2) + ^{(N- 1)} C_(N-1) 
Que es la suma del coeficiente binomial. 
= 2^(n-1)

// C++ program to count total number of ways
// to reach n-th stair with all jumps allowed
#include <bits/stdc++.h>
using namespace std;
 
     int calculateLeaps(int n)
    {
        if (n == 0)
            return 1;
        return (1 << (n - 1));
    }
 
// Driver code
int main()
{
    int calculateLeaps(int);
    std::cout << calculateLeaps(4) << std::endl;
    return 0;
}
 
// This code is contributed by shivanisinghss2110.

// Java program to count total number of ways
// to reach n-th stair with all jumps allowed
class GFG {
    static int calculateLeaps(int n)
    {
        if (n == 0)
            return 1;
        return (1 << (n - 1));
    }
 
    // Driver code
    public static void main(String[] args)
    {
        System.out.println(calculateLeaps(4));
    }
}
// This code is contributed by Anant Agarwal.

# python3 program to count
# total number of ways
# to reach n-th stair with
# all jumps allowed
 
def calculateLeaps(n):
    if (n == 0):
        return 1;
    return (1 << (n - 1));
 
# Driver code
print(calculateLeaps(4));
 
# This code is contributed
# by mits

// C# program to count total number of ways
// to reach n-th stair with all jumps allowed
using System;
 
class GFG {
 
    // Function to calculate leaps
    static int calculateLeaps(int n)
    {
        if (n == 0)
            return 1;
        return (1 << (n - 1));
    }
 
    // Driver code
    public static void Main()
    {
        Console.WriteLine(calculateLeaps(4));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to count total
// number of ways to reach n-th
// stair with all jumps allowed
 
// Function to calculate leaps
function calculateLeaps($n)
{
    if ($n == 0)
        return 1;
    return (1 << ($n - 1));
}
 
// Driver code
echo calculateLeaps(4);
 
// This code is contributed by Sam007
?>

<script>
 
// javascript program to count total number of ways
// to reach n-th stair with all jumps allowed
 
function calculateLeaps(n)
{
    if (n == 0)
        return 1;
    return (1 << (n - 1));
}
 
// Driver code
document.write(calculateLeaps(4));
 
// This code is contributed by Amit Katiyar
</script>

Producción:  

8

Complejidad de tiempo: O(1)

Espacio auxiliar: O(1)
Este artículo es una contribución de Partha Pratim Mallik . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.