Padovan Sequence

 #include <bits/stdc++.h>

using namespace std;

/* Padovan Sequence

Padovan Sequence similar to Fibonacci sequence with 

similar recursive structure. The recursive formula is,

  P(n) = P(n-2) + P(n-3)

  P(0) = P(1) = P(2) = 1  

Padovan Sequence: 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21..

For Padovan Sequence:

P(0) = P1 = P2 = 1 ,

P(7) = P(5) + P(4)

     = P(3) + P(2) + P(2) + P(1)

     = P(2) + P(1) + 1 + 1 + 1

     = 1 + 1 + 1 + 1 + 1 

     = 5

  

*/

int P_S(int n){

int n1 = 1,n2 = 1,n3 = 1,next = 1;

for(int i = 3;i<=n ;i++){

    next = n1 + n2;

    n1 = n2;

    n2 = n3;

    n3 = next;

}

return next;

}

int main()

{

 int n;

 cin >> n;

 cout << P_S(n) << endl;

    return 0;

}