Unable to pass the test case

#1

I have used DP to solve the problem and my logic seems correct but I don’t know where the error is in my code due to which the test case is not passing

#include
using namespace std;

void fillArray(int arr[],int maxVal,int n){
int a[maxVal+1];
a[0] = 0;
a[1] = 2;
a[2] = 3;

for(int i=3;i<=maxVal;i++){
    a[i] = a[i-1]+a[i-2];
}

for(int i=0;i<n;i++){
    cout<<"#"<<arr[i]<<"\t:\t"<<a[arr[i]]<<endl;
}

return;

}

int main() {
int n,max=0,arr[45];
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
max = (arr[i]>max) ? arr[i] : max;
}
fillArray(arr,max,n);
return 0;
}

#2

the correct approach for this question is
Let a[i] be the number of binary strings of length i which do not contain any two consecutive 1’s and which end in 0. Similarly, let b[i] be the number of such strings which end in 1. We can append either 0 or 1 to a string ending in 0, but we can only append 0 to a string ending in 1. This yields the recurrence relation:

a[i] = a[i - 1] + b[i - 1]
b[i] = a[i - 1]

#3

I didn’t understand your approach but isn’t my approach right using DP
i.e. a[i] = a[i-1]+a[i-2]

where a[i] represent all numbers possible of length i where no b’s are consecutive
with base cases as
a[1] = 2 //possible numbers using a and b are a,b
a[2] = 3 // possible numbers are aa,ab,ba

with the values of n as 4,10,33 my code generated the answers as 8,144,9227465 respectively.
Aren’t these answers correct??

#4

after going through your approach i understood your approach is correct too.
only thing you need to change is remove the tab spaces as display your result as shown in the sample output.don’t add those extra tab spaces

#5

Oh, that was a silly mistake on my part.
Thanks so much for the help, the code got submitted.