Número de formas de emparejar personas

Dado que hay p personas en un grupo. Cada persona puede unirse a la danza como individuo individual o en pareja con cualquier otra. La tarea es encontrar el número de formas diferentes en las que p personas pueden unirse al baile.
Ejemplos: 
 

Input : p = 3
Output : 4
Let the three people be P1, P2 and P3
Different ways are: {P1, P2, P3}, {{P1, P2}, P3},
{{P1, P3}, P2} and {{P2, P3}, P1}.

Input : p = 2
Output : 2
The groups are: {P1, P2} and {{P1, P2}}.

Enfoque: La idea es usar programación dinámica para resolver este problema. Hay dos situaciones: O la persona se une a la danza como individuo individual o en pareja. Para el primer caso el problema se reduce a encontrar la solución para las personas p-1. Para el segundo caso, hay opciones p-1 para seleccionar un individuo para emparejar y después de seleccionar un individuo para emparejar, el problema se reduce a encontrar una solución para p-2 personas ya que dos personas entre p ya están emparejadas. 
Entonces la fórmula para dp es: 
 

dp[p] = dp[p-1] + (p-1) * dp[p-2].

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

// CPP program to find number of ways to
// pair people in party
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find number of ways to
// pair people in party
int findWaysToPair(int p)
{
    // To store count of number of ways.
    int dp[p + 1];
 
    dp[1] = 1;
    dp[2] = 2;
 
    // Using the recurrence defined find
    // count for different values of p.
    for (int i = 3; i <= p; i++) {
        dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
    }
 
    return dp[p];
}
 
// Driver code
int main()
{
    int p = 3;
    cout << findWaysToPair(p);
    return 0;
}

// Java program to find number of ways to
// pair people in party
 
class GFG
{
     
// Function to find number of ways to
// pair people in party
static int findWaysToPair(int p)
{
    // To store count of number of ways.
    int dp[] = new int[p + 1];
 
    dp[1] = 1;
    dp[2] = 2;
 
    // Using the recurrence defined find
    // count for different values of p.
    for (int i = 3; i <= p; i++)
    {
        dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
    }
 
    return dp[p];
}
 
// Driver code
public static void main(String args[])
{
    int p = 3;
    System.out.println(findWaysToPair(p));
}
}
 
// This code is contributed by Arnab Kundu

# Python3 program to find number of
# ways to pair people in party
 
# Function to find number of ways
# to pair people in party
def findWays(p):
 
    # To store count of number of ways.
    dp = [0] * (p + 1)
    dp[1] = 1
    dp[2] = 2
 
    # Using the recurrence defined find
    # count for different values of p.
    for i in range(3, p + 1):
        dp[i] = (dp[i - 1] +
                   (i - 1) * dp[i - 2])
    return dp[p]
 
# Driver code
p = 3
print(findWays(p))
 
# This code is contributed by Shrikant13

// C# program to find number of ways to
// pair people in party
using System;
 
class GFG
{
 
// Function to find number of ways to
// pair people in party
public static int findWaysToPair(int p)
{
    // To store count of number of ways.
    int[] dp = new int[p + 1];
 
    dp[1] = 1;
    dp[2] = 2;
 
    // Using the recurrence defined find
    // count for different values of p.
    for (int i = 3; i <= p; i++)
    {
        dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
    }
    return dp[p];
}
 
// Driver code
public static void Main(string[] args)
{
    int p = 3;
    Console.WriteLine(findWaysToPair(p));
}
}
 
// This code is contributed by shrikanth13

<?php
// PHP program to find number of ways
// to pair people in party
 
// Function to find number of ways to
// pair people in party
function findWaysToPair($p)
{
    // To store count of number of ways.
    $dp = array();
 
    $dp[1] = 1;
    $dp[2] = 2;
 
    // Using the recurrence defined find
    // count for different values of p.
    for ($i = 3; $i <= $p; $i++)
    {
        $dp[$i] = $dp[$i - 1] +
                     ($i - 1) * $dp[$i - 2];
    }
 
    return $dp[$p];
}
 
// Driver code
$p = 3;
echo findWaysToPair($p);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
// Javascript program to find number of ways to
// pair people in party
 
// Function to find number of ways to
// pair people in party
function findWaysToPair(p)
{
    // To store count of number of ways.
    var dp = Array(p+1);
 
    dp[1] = 1;
    dp[2] = 2;
 
    // Using the recurrence defined find
    // count for different values of p.
    for (var i = 3; i <= p; i++) {
        dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
    }
 
    return dp[p];
}
 
// Driver code
var p = 3;
document.write( findWaysToPair(p));
 
// This code is contributed by noob2000.
</script>

4

Complejidad temporal: O(p) 
Espacio auxiliar: O(p)