Formas de pintar escaleras con dos colores de forma que dos contiguas no sean amarillas

Dadas n escaleras y tenemos 2 colores amarillo y verde, la tarea es que tenemos que pintar las escaleras dadas por el color dado con la condición de que no podemos pintar dos escalones amarillos uno detrás del otro.
Ejemplos: 
 

Input : n = 1
Output : 2
A single stair can be colored either
as green or yellow.

Input : n = 3
Output : 5

Caso 1: Cuando tengamos 1 escalera, podemos pintarla de amarillo o de verde. 
Caso 2: Cuando tenemos 2 escalones, podemos pintar el primer escalón de amarillo o verde, pero para el siguiente escalón solo podemos pintar de verde porque no podemos pintar dos escalones amarillos uno detrás del otro. Así que los casos totales son tres YG, GG, GY. 
Caso 3: Cuando tenemos 3 escaleras, podemos pintarlas de 5 maneras.
Si miramos más de cerca, podemos notar que sigue la serie de Fibonacci .
 

// C++ Program to find the number of ways to paint stairs
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of ways
int ways(int n)
{
    int W[n + 1];
 
    // take base case for 1 and 2
    W[1] = 2;
    W[2] = 3;
 
    for (int i = 3; i <= n; i++)
        W[i] = W[i - 1] + W[i - 2];
     
    return W[n];
}
 
// Driven code
int main()
{
    int n = 3;
    printf("%d", ways(n));
    return 0;
}

// java Program to find the number of
// ways to paint stairs
import java.io.*;
 
public class GFG {
     
    // Function to find the number of ways
    static int ways(int n)
    {
        int []W = new int[n+1];
     
        // take base case for 1 and 2
        W[1] = 2;
        W[2] = 3;
     
        for (int i = 3; i <= n; i++)
            W[i] = W[i - 1] + W[i - 2];
         
        return W[n];
    }
     
    // Driven code
    static public void main (String[] args)
    {
        int n = 3;
         
        System.out.println(ways(n));
    }
}
 
// This code is contributed by vt_m.

# Python3 code to find the number
# of ways to paint stairs
 
# Function to find the number of ways
def ways( n ):
    W = list()
     
    # take base case for 1 and 2
    W.append(0)
    W.append(2)
    W.append(3)
     
    i = 3
    while i <= n:
        W.append(W[i - 1] + W[i - 2])
        i = i + 1
         
    return W[n]
 
# Driver code
n = 3
print(ways(n))
 
# This code is contributed by "Sharad_Bhardwaj".

// C# Program to find the number of
// ways to paint stairs
using System;
 
public class GFG {
     
    // Function to find the number of ways
    static int ways(int n)
    {
        int []W =new int[n+1];
     
        // take base case for 1 and 2
        W[1] = 2;
        W[2] = 3;
     
        for (int i = 3; i <= n; i++)
            W[i] = W[i - 1] + W[i - 2];
         
        return W[n];
    }
     
    // Driven code
    static public void Main ()
    {
        int n = 3;
     
        Console.WriteLine(ways(n));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP Program to find the
// number of ways to paint stairs
 
// Function to find the
// number of ways
function ways($n)
{
 
    // take base case
    // for 1 and 2
    $W[1] = 2;
    $W[2] = 3;
 
    for ($i = 3; $i <= $n; $i++)
        $W[$i] = $W[$i - 1] +
                 $W[$i - 2];
     
    return $W[$n];
}
 
// Driven code
$n = 3;
echo ways($n);
 
// This code is contributed by ajit
?>

<script>
 
// Javascript Program to find the number of
// ways to paint stairs
 
    // Function to find the number of ways
    function ways(n)
    {
        let W = [];
       
        // take base case for 1 and 2
        W[1] = 2;
        W[2] = 3;
       
        for (let i = 3; i <= n; i++)
            W[i] = W[i - 1] + W[i - 2];
           
        return W[n];
    }
 
// Driver code
 
        let n = 3;
           
        document.write(ways(n));
           
</script>

Producción : 
 

5

Complejidad del tiempo: O(n) 
Espacio adicional: O(n)
Podemos resolver este problema en el tiempo O(Log n) usando también la solución de exponenciación matricial para el número n-ésimo de Fibonacci .