Find Loveable strings containing permutations of ANU

Anubhav has a crush on Anu. Therefore he likes the letters A,N and U the most.

He likes those strings which consists of only A N U

According to him, the strings containing A,N and U only are "LOVABLE" If they contain either of these patterns:


1) ANU


2) AUN


3) NAU


4) NUA


5) UAN


6) UNA


He asks you to find out how many LOVABLE strings are there of length N.


Note: Assume all strings are made of A,N,U. Consider all other alphabets as non-existent.


Input format: First line contains T the number of test cases. Next T lines contain a single integer N, denoting the length of string


Output format: Output the count of LOVABLE strings of length N in a single line for each test case


Constraints:


1<= T <= 30


1<= N <= 30

Solution : 

// Online C++ compiler to run C++ program online #include<bits/stdc++.h> using namespace std; class Solution{         int a = 1;     int n1 = 7;     int u = 3;     public :     int solve(int n , int pre , int pre_pre , int sum , bool x  )     {           if(n ==0)         {             if(x)             return 1;             return 0;         }         long long result =0;         if(sum == a + pre + pre_pre )         {             result += solve(n-1 , a , pre , sum , true );         }         else         result += solve(n-1 , a , pre , sum , x);                 if(sum == n1 + pre + pre_pre )         {             result += solve(n-1 , n1 , pre , sum , true );         }         else         result += solve(n-1 , n1 , pre , sum , x);                 if(sum == u + pre + pre_pre )         {             result += solve(n-1 , u , pre , sum , true );         }         else         result += solve(n-1 , u , pre , sum , x);                 return result;                                     }     int Loveable(int  n )     {         if(n == 0 || n==1 || n==2)         {             return 0;         }         return solve(n , -1 , -1 , 11 , false);                     } }; int main() {         Solution s ;     int n = 4;     int x = s.Loveable(n);     cout << x << " "<<"\n"; }

The dynamic programming solution will be uploaded soon, Stay tuned.