Count Number of Binary Strings. Why giving wrong answer?

#1

import java.util.*;
public class Main {
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
StringBuilder ans=new StringBuilder();
int t=sc.nextInt();
for(int f=0;f<t;f++){
int n=sc.nextInt();
int dp[]=new int[1000];
dp[1]=2;
dp[2]=3;
int k=fun(n,dp);
ans.append(k+"\n");
}
System.out.print(ans);
}
public static int fun(int n,int dp[]){
if(dp[n]!=0)
return dp[n];
else
dp[n]=fun(n-1,dp)+fun(n-2,dp);
return dp[n];
}
}

#2

@Anubhav44044 your DP recurrence is incorrect!
maintain two arrays (say one[] and zero[]) which stores number of substrings ending with 1 and 0.
so answer for x length is:

  1. zero[x-1] + one[x-1] // ending with 0
  2. zero[x-1] // ending with 1
    so answer will be 2*zero[x-1] + one[x-1]