Problem Link:
Author: Parth Trehan
Editorialist: Parth Trehan
Difficulty:
Easy-Medium
Prerequisites:
DP,Maths
Problem:
Given N number of enitities, we need to find the number of ways those entities could either occur independently or in pair.
Explanation:
We are given N entities as an integer input. We need to calculate the number of ways theses entities could either exist independently or in pair. For this purpose, we maintain an array which stores the number of ways that are possible when the enitities are equal to the indeces of the array. Now, for a single entity, it can either exist in a pair or it can exist independently. If there is just one entity, it always occurs independently and if there are two entities, there are two ways for them to exist. Using these two as the base conditions and the recurrence relation dp[i] = (dp[i-1] + (i-1)*dp[i-2]) mod 1000000007 , we can calculate the number of ways and store them in the array. The required array is stored in dp[n].