Given N friends, each one can remain single or can be paired up with some other friend. Each friend can be paired only once. Find out the total number of ways in which friends can remain single or can be paired up.
Note: Since answer can be very large, return your answer mod 10^9+7.
Example 1:
Input:N = 3
Output: 4
Explanation:
{1}, {2}, {3} : All single
{1}, {2,3} : 2 and 3 paired but 1 is single.
{1,2}, {3} : 1 and 2 are paired but 3 is single.
{1,3}, {2} : 1 and 3 are paired but 2 is single.
Note that {1,2} and {2,1} are considered same.
Example 2: 
Input: N = 2
Output: 2
Explanation:
{1} , {2} : All single.
{1,2} : 1 and 2 are paired.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countFriendsPairings() which accepts an integer n and return number of ways in which friends can remain single or can be paired up.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def countFriendsPairings(self, n):

        # code here 

Solutions:
class Solution:

	def countFriendsPairings(self, n):
		if n <= 2:
			return n
		dp = [0 for i in range(n)]
		dp[0] = 1
		dp[1] = 2
		for i in range(2, n):
			dp[i] = (dp[i - 1] + i * dp[i - 2]) % (10 ** 9 + 7)
		return dp[n - 1]


class Solution:

	def countFriendsPairings(self, n):
		if n <= 2:
			return n
		(a, b) = (1, 2)
		for i in range(3, n + 1):
			c = (i - 1) * a + b
			(a, b) = (b, c)
		return c % 1000000007


class Solution:

	def countFriendsPairings(self, n):
		mod = 1000000000.0 + 7
		dp = [0] * (n + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % mod
		return int(dp[n])


class Solution:

	def countFriendsPairings(self, n):
		mm = 1000000007
		dp = {}
		dp[0] = 1
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2] % mm) % mm
		return dp[n]


import sys
sys.setrecursionlimit(100000000)

class Solution:
	cache = dict()

	def countFriendsPairings(self, n):
		if n == 0 or n == 1:
			return 1
		if n in self.cache:
			return self.cache[n]
		value = self.countFriendsPairings(n - 1) + (n - 1) * self.countFriendsPairings(n - 2)
		value = value % (10 ** 9 + 7)
		if n not in self.cache:
			self.cache[n] = value
		return value


M = 10 ** 9 + 7

class Solution:

	def countFriendsPairings(self, n):
		(a0, a1) = (1, 1)
		for i in range(2, n + 1):
			(a0, a1) = (a1, ((i - 1) * a0 % M + a1) % M)
		return a1


class Solution:

	def countFriendsPairings(self, N):
		if N <= 2:
			return N
		mod = int(1000000000.0 + 7)
		dp = [0] * (N + 1)
		dp[1] = 1
		dp[2] = 2
		for i in range(3, N + 1):
			dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % mod
		return dp[N]


class Solution:

	def countFriendsPairings(self, n):
		prev = 1
		curr = 2
		if n == 1:
			return 1
		if n == 2:
			return 2
		for i in range(3, n + 1):
			next = curr + (i - 1) * prev
			prev = curr
			curr = next
		return next % 1000000007


class Solution:

	def countFriendsPairings(self, n):
		(mem, mod) = ({}, 10 ** 9 + 7)

		def ways(n):
			if n <= 1:
				return 1
			if n in mem:
				return mem[n]
			mem[n] = (ways(n - 1) + (n - 1) * ways(n - 2)) % mod
			return mem[n]
		return ways(n)


class Solution:

	def countFriendsPairings(self, n):
		dp = [-1] * (n + 1)
		return self.solve(n, dp)

	def solve(self, n, dp):
		if n == 1 or n == 0:
			return 1
		if dp[n] != -1:
			return dp[n]
		oneP = self.solve(n - 1, dp)
		doubleP = (n - 1) * self.solve(n - 2, dp)
		dp[n] = (oneP + doubleP) % 1000000007
		return dp[n]


class Solution:

	def countFriendsPairings(self, n):
		mod = 10 ** 9 + 7
		if n == 1:
			return 1
		if n == 2:
			return 2
		dp1 = 1
		dp2 = 2
		for i in range(3, n + 1):
			temp = dp2
			dp2 = (dp2 % mod + (i - 1) * dp1 % mod) % mod
			dp1 = temp
		return dp2


class Solution:

	def countFriendsPairings(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		n1 = 1
		n2 = 2
		for i in range(3, n + 1):
			curr = (n2 + (i - 1) * n1) % (10 ** 9 + 7)
			n1 = n2
			n2 = curr
		return curr


class Solution:

	def countFriendsPairings(self, n):
		dp = [-1] * (10 ** 4 + 1)
		dp[1] = 1
		dp[2] = 2
		for i in range(3, n + 1):
			dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % (10 ** 9 + 7)
		return dp[n]


class Solution:

	def countFriendsPairings(self, n):
		dp = [-1] * (10 ** 4 + 1)

		def state(k):
			if k <= 2:
				return k
			if dp[k] != -1:
				return dp[k]
			ans_r = (state(k - 1) + (k - 1) * state(k - 2)) % (10 ** 9 + 7)
			dp[k] = ans_r
			return dp[k]
		return state(n)


class Solution:

	def countFriendsPairings(self, n):
		if n <= 2:
			return n
		(x, y) = (1, 2)
		for i in range(3, n + 1):
			temp = (i - 1) * x + y
			(x, y) = (y, temp)
		return temp % (10 ** 9 + 7)


class Solution:

	def countFriendsPairings(self, n):
		(prevprev, prev) = (1, 1)
		for i in range(2, n + 1):
			curr = prev + (i - 1) * prevprev
			prevprev = prev
			prev = curr
		return prev % (10 ** 9 + 7)


class Solution:

	def countFriendsPairings(self, n):
		dp = [-1] * (n + 1)
		dp[0] = 1

		def fun(n):
			if n == 1:
				return 1
			if dp[n] != -1:
				return dp[n]
			dp[n] = (fun(n - 1) % 1000000007 + (n - 1) * fun(n - 2) % 1000000007) % 1000000007
			return dp[n]
		return fun(n)


class Solution:

	def countFriendsPairings(self, n):
		dp = [-1] * (n + 1)

		def finsol(n):
			if n <= 0:
				return 0
			if n == 1:
				return 1
			if n == 2:
				return 2
			if dp[n] != -1:
				return dp[n]
			ans = finsol(n - 1) % 1000000007
			ans2 = finsol(n - 2) % 1000000007
			ans2 = (n - 1) * ans2 % 1000000007
			ans = (ans + ans2) % 1000000007
			dp[n] = ans
			return ans
		return finsol(n)


class Solution:

	def countFriendsPairings(self, n):
		if n <= 2:
			return n
		dp = [0] * (n + 1)
		dp[1] = 1
		dp[2] = 2
		for i in range(3, len(dp)):
			dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % 1000000007
		return dp[n]


class Solution:

	def countFriendsPairings(self, n):
		dp = {}

		def solve(n):
			if n in dp:
				return dp[n] % 1000000007
			if n <= 2:
				dp[n] = n
				return dp[n]
			dp[n] = solve(n - 1) + (n - 1) * solve(n - 2)
			return dp[n] % 1000000007
		return solve(n) % 1000000007


class Solution:

	def countFriendsPairings(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		first = 1
		second = 2
		for i in range(3, n + 1):
			answer = (i - 1) * first + second
			(first, second) = (second, answer)
		return answer % (10 ** 9 + 7)


class Solution:

	def countFriendsPairings(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		first_element = 1
		second_element = 2
		for i in range(3, n + 1):
			answer = (i - 1) * first_element + second_element
			(first_element, second_element) = (second_element, answer)
		return answer % (10 ** 9 + 7)


class Solution:

	def countFriendsPairings(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		a = 1
		b = 2
		for i in range(3, n + 1):
			c = (i - 1) * a + b
			(a, b) = (b, c)
		return c % (10 ** 9 + 7)


class Solution:

	def countFriendsPairings(self, n):
		mod = 10 ** 9 + 7
		memo = {}

		def pair(i):
			nonlocal mod
			if i == 0:
				return 1
			if i < 0:
				return 0
			if i in memo:
				return memo[i]
			memo[i] = pair(i - 1) % mod + (i - 1) * pair(i - 2) % mod
			return memo[i] % mod
		return pair(n)


class Solution:

	def countFriendsPairings(self, n):
		dp = [None] * (n + 1)
		if n == 1 or n == 2:
			return n
		(dp[0], dp[1], dp[2]) = (0, 1, 2)
		mod = pow(10, 9) + 7
		for i in range(3, n + 1):
			dp[i] = (dp[i - 1] % mod + (i - 1) % mod * dp[i - 2] % mod) % mod
		return dp[n]


class Solution:

	def countFriendsPairings(self, n):

		def way(n, dp):
			if n <= 2:
				return n
			if dp[n] != -1:
				return dp[n]
			sin = way(n - 1, dp)
			pa = (n - 1) * way(n - 2, dp)
			dp[n] = (sin + pa) % 1000000007
			return dp[n]
		dp = [-1 for i in range(n + 1)]
		return way(n, dp)


class Solution:

	def countFriendsPairings(self, n):
		g = {}

		def recr(n):
			if n in g:
				return g[n]
			if n == 1 or n == 2:
				return n
			ans = (recr(n - 1) + (n - 1) * recr(n - 2)) % (10 ** 9 + 7)
			g[n] = ans
			return ans
		return recr(n)


class Solution:

	def countFriendsPairings(self, n):
		if n == 1:
			return 1
		arr = [1] * (n + 1)
		m = 10 ** 9 + 7
		for i in range(2, n + 1):
			arr[i] = (arr[i - 1] % m + (i - 1) * arr[i - 2] % m) % m
		return arr[n] % m


class Solution:

	def countFriendsPairings(self, n):
		mod = 1000000007
		ans = [0, 1]
		for i in range(1, n + 1):
			ans.append((ans[-2] * (i - 1) + ans[-1]) % mod)
		return ans[-1]


from functools import lru_cache

class Solution:

	def countFriendsPairings(self, n):
		if n <= 2:
			return n
		mod = 1000000007
		(prev1, prev2) = (1, 2)
		for i in range(3, n + 1):
			c = (prev2 + (i - 1) * prev1 % mod) % mod
			prev1 = prev2
			prev2 = c
		return prev2


from functools import lru_cache

class Solution:

	def countFriendsPairings(self, n):
		mod = 1000000007

		@lru_cache(None)
		def fun(n):
			if n <= 2:
				return n
			return (fun(n - 1) + (n - 1) * fun(n - 2) % mod) % mod
		return fun(n) % mod


class Solution:

	def countFriendsPairings(self, n):
		dp = [0] * (n + 1)
		mod = 10 ** 9 + 7

		def fun(n, dp):
			if dp[n]:
				return dp[n]
			if n <= 1:
				dp[n] = 1
				return dp[n]
			dp[n] = fun(n - 1, dp) % mod + (n - 1) * fun(n - 2, dp) % mod
			dp[n] %= mod
			return dp[n]
		return fun(n, dp)


class Solution:

	def countFriendsPairings(self, N):
		dp = [0 for i in range(N + 1)]
		if N <= 2:
			return N
		Power = pow(10, 9) + 7
		for i in range(N + 1):
			if i <= 2:
				dp[i] = i
			else:
				dp[i] = (1 * dp[i - 1] + (i - 1) * dp[i - 2]) % Power
		return dp[N]


class Solution:

	def solve(self, n, dp):
		mod = 1000000007
		if n == 0:
			return 1
		if n < 0:
			return 0
		if dp[n] != -1:
			return dp[n]
		spair = self.solve(n - 1, dp)
		dpair = (n - 1) * self.solve(n - 2, dp)
		dp[n] = (spair + dpair) % mod
		return dp[n]

	def countFriendsPairings(self, n):
		dp = [-1 for i in range(n + 1)]
		return self.solve(n, dp)


class Solution:

	def countFriendsPairings(self, n):
		if n < 3:
			return n
		d = [0] * (n + 1)
		d[1] = 1
		d[2] = 2
		m = 1000000007
		for i in range(3, n + 1):
			d[i] = (d[i - 1] + (i - 1) * d[i - 2]) % m
		return d[n]


mod = 10 ** 9 + 7

class Solution:

	def countFriendsPairings(self, n):
		if n <= 2:
			return n
		prev1 = 2
		prev2 = 1
		for i in range(3, n + 1):
			ans = (prev1 % mod + (i - 1) % mod * (prev2 % mod) % mod) % mod
			prev2 = prev1
			prev1 = ans
		return prev1
		return dp[n]


mod = 10 ** 9 + 7

class Solution:

	def countFriendsPairings(self, n):

		def f(n):
			if n <= 2:
				return n
			if dp[n] != -1:
				return dp[n]
			ans = (f(n - 1) % mod + (n - 1) % mod * (f(n - 2) % mod) % mod) % mod
			dp[n] = ans
			return dp[n]
		dp = [-1] * (n + 1)
		return f(n)


class Solution:

	def solve(self, dp, n):
		if n == 0:
			return 1
		if n < 0:
			return 0
		if dp[n] != -1:
			return dp[n]
		single = self.solve(dp, n - 1)
		pair = (n - 1) * self.solve(dp, n - 2)
		dp[n] = (single + pair) % (10 ** 9 + 7)
		return dp[n]

	def countFriendsPairings(self, n):
		dp = [-1 for _ in range(n + 1)]
		ans = self.solve(dp, n)
		return ans


mod = 1000000007

class Solution:

	def solveRecursion(self, n):
		if n == 0:
			return 1
		if n < 0:
			return 0
		return (self.solveRecursion(n - 1) + (n - 1) * self.solveRecursion(n - 2)) % mod

	def topDown(self, n):
		memory = [-1] * (n + 1)
		return self.TopDownDP(n, memory)

	def TopDownDP(self, n, memory):
		if n == 0:
			return 1
		if n < 0:
			return 0
		if memory[n] == -1:
			memory[n] = (self.TopDownDP(n - 1, memory) + (n - 1) * self.TopDownDP(n - 2, memory)) % mod
		return memory[n]

	def BottomUpDp(self, n):
		memory = [0] * (n + 1)
		memory[0] = 1
		memory[1] = 1
		for i in range(2, n + 1):
			memory[i] = (memory[i - 1] + (i - 1) * memory[i - 2]) % mod
		return memory[n]

	def optimizedBottomUp(self, n):
		friend1 = 1
		friend2 = 1
		ans = 1
		for i in range(2, n + 1):
			ans = (friend2 + (i - 1) * friend1) % mod
			friend1 = friend2
			friend2 = ans
		return ans

	def countFriendsPairings(self, n):
		return self.optimizedBottomUp(n)


class Solution:

	def countFriendsPairings(self, n):
		t = [0] * (n + 1)
		for i in range(n + 1):
			if i <= 2:
				t[i] = i
			else:
				t[i] = (t[i - 1] + (i - 1) * t[i - 2]) % 1000000007
		return t[n] % 1000000007