Cuente las posibles combinaciones de pares con elementos adyacentes de los primeros N números

Dado un número N, la tarea es contar todas las combinaciones posibles de pares formados usando elementos adyacentes.
Nota : si un elemento ya existe en un par, no se puede seleccionar en el siguiente par. Por ejemplo: para {1,2,3}: {1,2} y {2,3} no se considerarán una combinación correcta.
Ejemplos: 
 

Input : N = 4
Output : 5
Explanation : If N = 4, the possible combinations are:
{1}, {2}, {3}, {4}
{1, 2}, {3, 4}
{1}, {2, 3}, {4}
{1}, {2}, {3, 4}
{1, 2}, {3}, {4}

Input : N = 5
Output : 8

Enfoque: Dividir el problema en subproblemas más pequeños. Si hay N números, y hay dos casos, o un número está solo o está en un par, si un número está solo, encuentre las formas de emparejar (n-1) números que quedan, o si está en un par , encuentre las formas de emparejar (n-2) números que quedan. Si solo quedan 2 números pueden generar 2 combinaciones solos o en pareja, y si queda un solo número será en singleton, por lo que solo queda 1 combinación.
A continuación se muestra la implementación del enfoque anterior:
 

#include <bits/stdc++.h>
using namespace std;
// Function to count the number of ways
int ways(int n)
{
    // If there is a single number left
    // it will form singleton
    if (n == 1) {
        return 1;
    }
    // if there are just 2 numbers left,
    // they will form a pair
    if (n == 2) {
        return 2;
    }
    else {
        return ways(n - 1) + ways(n - 2);
    }
}
 
// Driver Code
int main()
{
    int n = 5;
 
    cout << "Number of ways = " << ways(n);
 
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG
{
     
// Function to count the number of ways
static int ways(int n)
{
    // If there is a single number left
    // it will form singleton
    if (n == 1)
    {
        return 1;
    }
     
    // if there are just 2 numbers left,
    // they will form a pair
    if (n == 2)
    {
        return 2;
    }
    else
    {
        return ways(n - 1) + ways(n - 2);
    }
}
 
// Driver Code
public static void main (String[] args)
{
    int n = 5;
     
    System.out.println("Number of ways = " + ways(n));
}
}

# Python3 code implementation of the above program
 
# Function to count the number of ways
def ways(n) :
     
    # If there is a single number left
    # it will form singleton
    if (n == 1) :
        return 1;
     
    # if there are just 2 numbers left,
    # they will form a pair
    if (n == 2) :
        return 2;
     
    else :
        return ways(n - 1) + ways(n - 2);
 
# Driver Code
if __name__ == "__main__" :
 
    n = 5;
 
    print("Number of ways = ", ways(n));
 
# This code is contributed by AnkitRai01

// C# implementation of the above code
using System;
 
class GFG
{
     
// Function to count the number of ways
static int ways(int n)
{
    // If there is a single number left
    // it will form singleton
    if (n == 1)
    {
        return 1;
    }
     
    // if there are just 2 numbers left,
    // they will form a pair
    if (n == 2)
    {
        return 2;
    }
    else
    {
        return ways(n - 1) + ways(n - 2);
    }
}
 
// Driver Code
public static void Main()
{
    int n = 5;
     
    Console.WriteLine("Number of ways = " + ways(n));
}
}
 
// This code is contributed by AnkitRai01

<script>
    // Javascript implementation of the above code
     
    // Function to count the number of ways
    function ways(n)
    {
        // If there is a single number left
        // it will form singleton
        if (n == 1)
        {
            return 1;
        }
 
        // if there are just 2 numbers left,
        // they will form a pair
        if (n == 2)
        {
            return 2;
        }
        else
        {
            return ways(n - 1) + ways(n - 2);
        }
    }
     
    let n = 5;
       
    document.write("Number of ways = " + ways(n));
 
// This code is contributed by suresh07.
</script>

Number of ways = 8

Complejidad de tiempo: O(2^N)
Espacio auxiliar: O(N)

Otro enfoque:

Podemos almacenar los valores calculados en una array y reutilizar los epílogos del valor calculado, lo que haría que el programa fuera eficiente.

Implementación del enfoque anterior:

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// vector to store the computed values
vector<int> dp;
 
// Function to count the number of ways
int ways(int n)
{
    // If there is a single number left
    // it will form singleton
      int& res = dp[n];
       
      // return the stored value
      // if the value is already computed
      if(res!=-1)
          return res;
   
      // base case
    if (n == 1) {
        return res=1;
    }
   
    // if there are just 2 numbers left,
    // they will form a pair
    if (n == 2) {
        return res=2;
    }
    else {
           
        return res = ways(n - 1) + ways(n - 2);
    }
}
 
// Driver Code
int main()
{
    int n = 5;
    dp = vector<int>(n + 1,-1);
    cout << "Number of ways = " << ways(n);
 
    return 0;
}

// Java implementation of the above approach
 
class GFG {
 
    // vector to store the computed values
    static int[] dp;
 
    // Function to count the number of ways
    static int ways(int n)
    {
        // If there is a single number left
        // it will form singleton
        int res = dp[n];
 
        // return the stored value
        // if the value is already computed
        if (res != -1)
            return res;
 
        // base case
        if (n == 1) {
            return res = 1;
        }
 
        // if there are just 2 numbers left,
        // they will form a pair
        if (n == 2) {
            return res = 2;
        }
        else {
            return res = ways(n - 1) + ways(n - 2);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 10;
        dp = new int[n + 1];
        Arrays.fill(dp, -1);
        System.out.println("Number of ways = " + ways(n));
    }
}
 
// This code is contributed by jainlovely450

# Python3 implementation of the above approach
 
# vector to store the computed values
dp=[]
 
# Function to count the number of ways
def ways(n):
    # If there is a single number left
    # it will form singleton
    res = dp[n]
     
    # return the stored value
    # if the value is already computed
    if(res!=-1):
        return res
 
    # base case
    if (n == 1) :
        res=1
        return res
     
   
    # if there are just 2 numbers left,
    # they will form a pair
    if (n == 2) :
        res=2
        return res
     
    else :         
        res = ways(n - 1) + ways(n - 2)
        return res
     
 
 
# Driver Code
if __name__ == '__main__':
    n = 5
    dp = [-1]*(n + 1)
    print("Number of ways =",ways(n))

<script>
// JavaScript implementation of the above approach
 
// array to store the computed values
let dp = [];
 
// Function to count the number of ways
function ways(n)
{
    // If there is a single number left
    // it will form singleton
     
      let res = dp[n];
       
      // return the stored value
      // if the value is already computed
      if(res!=-1)
          return res;
   
      // base case
      if (n == 1) {
         res = 1;
         return res;
      }
   
    // if there are just 2 numbers left,
    // they will form a pair
      if (n == 2) {
        res = 2;
      }
      else { 
        res = ways(n - 1) + ways(n - 2);
      }
 
      dp[n] = res;
      return res;
}
 
// Driver Code
let n = 5;
dp = new Array(n+1).fill(-1);
document.write(dp);
document.write("Number of ways = " + ways(n));
 
// This code is contributed by shinjanpatra
</script>

Number of ways = 8

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)