Contar caminos para llegar a la N-ésima escalera | Conjunto-2

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.

Nth-escaleras

Ejemplos: 

Entrada: N = 1
Salida: 1
Explicación: Solo hay una manera de subir la primera escalera

Entrada: N= 2
Salida: 2
Explicación: Hay dos caminos y la secuencia para subir al escalón N es: (1, 2), (2)

Entrada: N = 4
Salida: 5
Explicación: Hay cinco formas posibles y la secuencia para subir a la escalera N es:
(1, 2, 3, 4), (1, 2, 4), (2, 3, 4) , (1, 3, 4), (2, 4) 

La programación dinámica y la ventana deslizante y varios otros enfoques se analizan en el Conjunto 1 de este problema. Pero este enfoque tendrá un mejor espacio auxiliar general.

Enfoque: Este problema se puede resolver con una mayor complejidad espacial en base a la siguiente observación:

Si se observa de cerca, el valor del estado actual ( i ) depende de dos estados: el valor del estado anterior (i – 1) y el valor del estado (i – 2).
En lugar de usar espacio adicional, solo se pueden usar dos variables para almacenar los valores de los dos estados mencionados anteriormente.
Como uno puede subir un escalón o dos peldaños a la vez, el i-ésimo valor de estado es la suma de los valores de (i – 1) y (i – 2) estado.

Siga la ilustración dada a continuación para una mejor comprensión.

Inicialmente, hay una forma de llegar al 1er escalón y la secuencia para subir al 1er escalón es: (1)
Hay dos formas de llegar al 2º escalón y la secuencia para subir al 2º escalón es: (1, 2), (2)

Para el 3er escalón:
        => Número de formas de llegar al 3er escalón = anterior1 + anterior2. es decir, actual = 2 + 1 = 3.
        => anterior2 = anterior1 = 2. anterior1 = actual = 3

Para el 4° escalón:
        => Número de formas de llegar al 3° escalón = prev1 + prev2. es decir, actual = 3 + 2 = 5.
        => anterior2 = anterior1 = 3. anterior1 = actual = 5

Para el 5° escalón:
        => Número de formas de llegar al 3° escalón = prev1 + prev2. es decir, actual = 5 + 3 = 8.
        => anterior2 = anterior1 = 5. anterior1 = actual = 8

Para el 6° escalón:
        => Número de formas para llegar al 3° escalón = prev1 + prev2. es decir, actual = 8 + 5 = 13.
        => anterior2 = anterior1 = 8. anterior1 = actual = 13

A continuación se muestra la representación de la imagen de cada paso de la explicación anterior:

 

Siga los pasos que se mencionan a continuación para resolver el problema:

• Declare dos variables (digamos, prev1 y prev2 ) para almacenar los dos estados anteriores para cualquier estado actual e inicialícelos con el número de formas de llegar al primer y segundo escalón.
• Iterar desde el tercer escalón hasta el escalón N :
  • Calcule el número de formas de llegar a la escalera actual como se muestra en la observación anterior.
  • Ahora actualice las variables prev1 y prev2 según la observación.
• Devuelve el valor de la N- ésima escalera obtenido como resultado.

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum number of steps
int minSteps(int N)
{
    // Can make 1 jump only
    if (N == 1)
        return 1;
 
    // Can jump like {2} and {1 + 1}
    // so two ways for n == 2;
    if (N == 2)
        return 2;
 
    int curr;
    int prev2 = 1;
    int prev1 = 2;
 
    // Iterate from 3rd stair to nth stair
    for (int i = 3; i <= N; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return curr;
}
 
// Driver code
int main()
{
    int N = 6;
 
    // Function call
    cout << minSteps(N);
    return 0;
}

// Java code to implement the approach
import java.util.*;
 
class GFG {
 
  // Function to find minimum number of steps
  static int minSteps(int N)
  {
    // Can make 1 jump only
    if (N == 1)
      return 1;
 
    // Can jump like {2} and {1 + 1}
    // so two ways for n == 2;
    if (N == 2)
      return 2;
 
    int curr = 0;
    int prev2 = 1;
    int prev1 = 2;
 
    // Iterate from 3rd stair to nth stair
    for (int i = 3; i <= N; i++) {
      curr = prev1 + prev2;
      prev2 = prev1;
      prev1 = curr;
    }
    return curr;
  }
 
  // Driver code
  public static void main (String[] args) {
    int N = 6;
 
    // Function call
    System.out.print(minSteps(N));
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python3 code to implement the approach
 
# Function to find the minimum number of steps
def minSteps(N):
 
    # Can make 1 jump only
    if N == 1:
        return 1
 
    # Can jump like {2} and {1 + 1}
    # so two ways for n == 2
    if N == 2:
        return 2
 
    prev1, prev2 = 2, 1
 
    # iterate from 3rd stair to nth star
    for i in range(3, N + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
 
    return curr
 
# Driver Code
N = 6
 
# Function call
print(minSteps(N))
 
# This code is contributed by phasing17

// C# code to implement the above approach
using System;
 
class GFG {
 
  // Function to find minimum number of steps
  static int minSteps(int N)
  {
    // Can make 1 jump only
    if (N == 1)
      return 1;
 
    // Can jump like {2} and {1 + 1}
    // so two ways for n == 2;
    if (N == 2)
      return 2;
 
    int curr = 0;
    int prev2 = 1;
    int prev1 = 2;
 
    // Iterate from 3rd stair to nth stair
    for (int i = 3; i <= N; i++) {
      curr = prev1 + prev2;
      prev2 = prev1;
      prev1 = curr;
    }
    return curr;
  }
 
  // Driver code
  public static void Main()
  {
    int N = 6;
 
    // Function call
    Console.Write(minSteps(N));
  }
}
 
// This code is contributed by sanjoy_62.

<script>
    // JavaScript code to implement the approach
 
    // Function to find minimum number of steps
    const minSteps = (N) => {
     
        // Can make 1 jump only
        if (N == 1)
            return 1;
 
        // Can jump like {2} and {1 + 1}
        // so two ways for n == 2;
        if (N == 2)
            return 2;
 
        let curr;
        let prev2 = 1;
        let prev1 = 2;
 
        // Iterate from 3rd stair to nth stair
        for (let i = 3; i <= N; i++) {
            curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return curr;
    }
 
    // Driver code
    let N = 6;
 
    // Function call
    document.write(minSteps(N));
 
// This code is contributed by rakeshsahni
 
</script>

13

Complejidad de tiempo: O(N)
: O(1)