Conteo de subconjuntos de números enteros de 1 a N que no tienen elementos adyacentes

Dado un número entero N , la tarea es contar el número de subconjuntos formados a partir de una array de números enteros del 1 al N que no contiene elementos adyacentes. No se puede elegir un subconjunto si cumple la condición de elemento no adyacente , pero es posible agregar más elementos.
Ejemplos: 
 

Input: N = 4
Output: 3
Explanation:
Array is {1, 2, 3, 4}
So to satisfy the condition, the subsets formed are :
{1, 3}, {2, 4}, {1, 4}

Input: N = 5
Output: 4

Enfoque: 
Este problema se puede resolver usando Programación Dinámica . Para el último elemento, tenemos dos opciones, o lo incluimos o lo excluimos. Sea DP[i] el número de nuestros subconjuntos deseables que terminan en el índice i . 
 Entonces el siguiente subproblema se convierte en DP[i-3]
Entonces la relación DP se convierte en: 
 

DP[i] = DP[i-2] + DP[i-3]  

Pero, necesitamos observar los casos base: 
 

• Cuando N=0 , no podemos formar ningún subconjunto con 0 números.
• Cuando N=1 , podemos formar 1 subconjunto, {1}
• Cuando N=2 , podemos formar 2 subconjuntos, {1} , {2}
• Cuando N=3 , podemos formar 2 subconjuntos, {1, 3} , {2}

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ Code to count subsets not containing
// adjacent elements from 1 to N
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count subsets
int countSubsets(int N)
{
     
    if(N <= 2)
        return N;
         
    if(N == 3)
        return 2;
     
    int DP[N + 1] = {0};
     
    DP[0] = 0, DP[1] = 1, DP[2] = 2, DP[3] = 2;
     
    for (int i = 4; i <= N; i++) {
 
        DP[i] = DP[i - 2] + DP[i - 3];
    }
     
    return DP[N];
}
 
// Driver Code
int main()
{
    int N = 20;
     
    cout << countSubsets(N);
     
    return 0;
}

// Java code to count subsets not containing
// adjacent elements from 1 to N
class GFG{
 
// Function to count subsets
static int countSubsets(int N)
{
    if(N <= 2)
       return N;
         
    if(N == 3)
       return 2;
     
    int []DP = new int[N + 1];
     
    DP[0] = 0;
    DP[1] = 1;
    DP[2] = 2;
    DP[3] = 2;
     
    for(int i = 4; i <= N; i++)
    {
       DP[i] = DP[i - 2] + DP[i - 3];
    }
    return DP[N];
}
 
// Driver code
public static void main(String[] args)
{
    int N = 20;
     
    System.out.print(countSubsets(N));
}
}
 
// This code is contributed by sapnasingh4991

# Python3 Code to count subsets
# not containing adjacent elements
# from 1 to N
 
# Function to count subsets
def countSubsets(N):
 
    if(N <= 2):
        return N
 
    if(N == 3):
        return 2
 
    DP = [0] * (N + 1)
 
    DP[0] = 0
    DP[1] = 1
    DP[2] = 2
    DP[3] = 2
 
    for i in range(4, N + 1):
 
        DP[i] = DP[i - 2] + DP[i - 3]
 
    return DP[N]
 
# Driver Code
if __name__ == '__main__':
    N = 20
 
    print(countSubsets(N))
     
# This code is contributed by Mohit Kumar

// C# code to count subsets not containing
// adjacent elements from 1 to N
using System;
class GFG{
 
// Function to count subsets
static int countSubsets(int N)
{
    if(N <= 2)
        return N;
         
    if(N == 3)
        return 2;
     
    int []DP = new int[N + 1];
     
    DP[0] = 0;
    DP[1] = 1;
    DP[2] = 2;
    DP[3] = 2;
     
    for(int i = 4; i <= N; i++)
    {
        DP[i] = DP[i - 2] + DP[i - 3];
    }
    return DP[N];
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 20;
     
    Console.Write(countSubsets(N));
}
}
 
// This code is contributed by sapnasingh4991

<script>
// javascript code to count subsets not containing
// adjacent elements from 1 to N   
// Function to count subsets
    function countSubsets(N) {
        if (N <= 2)
            return N;
 
        if (N == 3)
            return 2;
 
        var DP = Array(N + 1).fill(0);
 
        DP[0] = 0;
        DP[1] = 1;
        DP[2] = 2;
        DP[3] = 2;
 
        for (i = 4; i <= N; i++) {
            DP[i] = DP[i - 2] + DP[i - 3];
        }
        return DP[N];
    }
 
    // Driver code
     
        var N = 20;
 
        document.write(countSubsets(N));
 
// This code contributed by gauravrajput1
</script>

265