Número de formas en que una array se puede llenar con 0 y 1 de manera que ningún elemento consecutivo sea 1

Dado un número N, encuentre el número de formas de construir una array de tamaño N tal que contenga solo 1 y 0, pero no hay dos índices consecutivos que tengan el valor 1 en ellos.

Ejemplos: 

Input  : 2
Output : 3
Explanation:
For n=2, the possible arrays are:
{0, 1} {1, 0} {0, 0}

Input  : 3
Output : 5
Explanation:
For n=3, the possible arrays are:
{0, 0, 0} {1, 0, 0} {0, 1, 0} {0, 0, 1} {1, 0, 1} 

Enfoque ingenuo: 
el enfoque básico de fuerza bruta sería construir todas las formas posibles en que la array se puede llenar con 1 y 0, y luego verificar si hay dos 1 consecutivos en la array, si los hay, no cuente esas arrays.
Dado que cada elemento tiene 2 valores posibles, 1 y 0, y hay n elementos totales, el número total de arrays sin ninguna restricción será de orden exponencial, es decir, 2 ⁿ .

Enfoque eficiente: 
si observamos un poco de cerca, podemos notar que se está formando un patrón en la entrada y la salida.
Para n = 1 , el número de formas es 2 , es decir, {0}, {1} 
para n = 2 , el número de formas es 3 
De manera similar,
para n = 3 el número de formas es 5 
para n = 4 el número de formas es 8
y así en… 

Sea T() la función que da el número de formas en que se puede llenar la array de tamaño n, luego obtenemos la siguiente relación de recurrencia 

T(n) = T(n-1) + T(n-2)

Y esta es la relación de recurrencia de la serie de Fibonacci< . 
Por lo tanto, la salida para cualquier n es igual al (n+2) ^enésimo término de la serie de Fibonacci a partir de 1.  Es
decir, 1 1 2 3 5 8 11…
Entonces ahora solo necesitamos calcular la secuencia de Fibonacci hasta el (n +2) ^th elementos y esa será la respuesta. 

La complejidad del tiempo es O(n) 

// C++ implementation of the
// above approach
#include <iostream>
using namespace std;
 
    // The total number of ways
    // is equal to the (n+2)th
    // Fibonacci term, hence we
    // only need to find that.
    int nth_term(int n)
    {
        int a = 1, b = 1, c = 1;
         
        // Construct fibonacci upto
        // (n+2)th term the first
        // two terms being 1 and 1
        for (int i = 0; i < n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
         
        return c;
    }
     
    // Driver Code
    int main()
    {
         
        // Take input n
        int n = 10;
        int c = nth_term(n);
         
        // printing output
        cout << c;
    }
 
// This code is contributed by Sumit Sudhakar.

// Java implementation of the
// above approach
class Main
{
  
    // The total number of ways
    // is equal to the (n+2)th
    // Fibonacci term, hence we
    // only need to find that.
    public static int nth_term(int n)
    {
        int a = 1, b = 1, c = 1;
          
        // Construct fibonacci upto
        // (n+2)th term the first
        // two terms being 1 and 1
        for (int i = 0; i < n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
          
        return c;
    }
      
    // Driver program
    public static void main(String[] args)
    {
        // Take input n
        int n = 10;
        int c = nth_term(n);
          
        // printing output
        System.out.println(c);
    }
}

# Python3 implementation of
# the above approach
 
# The total number of ways
# is equal to the (n+2)th
# Fibonacci term, hence we
# only need to find that.
def nth_term(n) :
     
    a = 1
    b = 1
    c = 1
     
    # Construct fibonacci upto
    # (n+2)th term the first
    # two terms being 1 and 1
    for i in range(0, n) :
        c = a + b
        a = b
        b = c
    return c
 
# Driver Code
 
# Take input n
n = 10
c = nth_term(n)
 
# printing output
print (c)
# This code is contributed by
# Manish Shaw (manishshaw1)

// C# implementation of the
// above approach
using System;
 
class GFG {
     
    // The total number of ways
    // is equal to the (n+2)th
    // Fibonacci term, hence we
    // only need to find that.
    static int nth_term(int n)
    {
        int a = 1, b = 1, c = 1;
         
        // Construct fibonacci upto
        // (n+2)th term the first
        // two terms being 1 and 1
        for (int i = 0; i < n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
         
        return c;
    }
     
    // Driver Code
    public static void Main()
    {
         
        // Take input n
        int n = 10;
        int c = nth_term(n);
         
        // printing output
        Console.WriteLine(c);
     
    }
}
     
// This code is contributed by Sam007

<?php
// PHP implementation of the
// above approach
 
    // The total number of ways
    // is equal to the (n+2)th
    // Fibonacci term, hence we
    // only need to find that.
    function nth_term($n)
    {
        $a = 1; $b = 1; $c = 1;
         
        // Construct fibonacci upto
        // (n+2)th term the first
        // two terms being 1 and 1
        for ($i = 0; $i < $n; $i++)
        {
            $c = $a + $b;
            $a = $b;
            $b = $c;
        }
         
        return $c;
    }
     
        // Driver Code
         
        // Take input n
        $n = 10;
        $c = nth_term($n);
         
        // printing output
        echo $c;
     
// This code is contributed by nitin mittal
?>

<script>
 
// Javascript implementation of the
// above approach
 
// The total number of ways
// is equal to the (n+2)th
// Fibonacci term, hence we
// only need to find that.
function nth_term(n)
{
    let a = 1, b = 1, c = 1;
       
    // Construct fibonacci upto
    // (n+2)th term the first
    // two terms being 1 and 1
    for(let i = 0; i < n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}
 
// Driver code
 
// Take input n
let n = 10;
let c = nth_term(n);
 
// Printing output
document.write(c);
 
// This code is contributed by rameshtravel07
 
</script>

Producción: 

144

Podemos optimizar aún más la solución anterior para trabajar en O (Log n) usando la solución de exponenciación matricial para encontrar el número n-th de Fibonacci (consulte los métodos 4, 5 y 6 del Programa para números de Fibonacci ).