Pet Store Dogs

                                 Pet Store Dogs

There is a per store in a city where dogs can be kept when their owners go for a long tour out of the city or the owners travel abroad. The cage in the pet store can accommodate two dogs. But certain dogs are very aggressive and must be kept along in a cage and hence cannot be put in the cage along with another dog. Given the number of dogs N and assuming that a given dog can be either aggressive or passive, the program must print the number of combinations in which can they be put in the cages (Assume the number of cages is always greater than N and hence there is no shortage of cages).

Input Format:
The first line contains N.

Output Format:
The first line contains the number of combinations in which the dogs can be put in the cages.

Boundary Conditions:
1 <= N <= 999

Example Input/Output 1:
Input:
4

Output:
10

Explanation:
4 dogs can be arranged in 10 combinations as shown below. The numbers inside parentheses indicates that the dogs are put in the same cage.
1 2 3 4
(1 2) 3 4
(1 2) (3 4)
(1 3) 2 4
(1 3) (2 4)
(1 4) 2 3
(1 4) (2 3)
1 (2 3) 4
1 3 (2 4)
1 2 (3 4)
Please note that 1 (2 3) 4 is same as 1 4 (2 3) or 4 (2 3) 1 or 4 (3 2) 1.

Code:

#include<stdio.h>

#include <stdlib.h>

int main()

{

int n;

scanf("%d",&n);

long long a[35];

a[1]=1;

a[0]=1;

for(int i=2;i<35;i++)

a[i]=a[i-1]+(i-1)*a[i-2];

printf("%lld",a[n]);

}

Please do comment If u have any Queries!