Run time error in count no of binary strings .how can i modify the code?

#1

int main() {
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int dp[100]={0};
dp[0]=1;
dp[1]=2;
for(int j=2;j<(1<<n);j++)
{
int flag=0;
for(int i=0;i<31;i++)
{
if(((j&(1<<i))!=0)&&((j&(1<<(i+1)))!=0))
{
flag=1;
break;
}
}
if(flag==1)
dp[j]=dp[j-1];
else
dp[j]=dp[j-1]+1;
}
int p=(1<<n)-1;
cout<<dp[p]<<endl;
}
}

#2

@neha_153
hello neha,
ur logic is correct but its time complexity is very high i.e 2^n*31.

a) one simple recursive approach is

ways(n)=ways(n-1 ) ( when 0 is placed at nth position )+ways(n-2) (when 1 is placed at nth position )

now u can use bottom up dp to calculate ways for string of length n