# Wrong answer in dp question CDQU5

plz somebody help me in getting this right .
I did dp[i] equals dp[i-2]+dp[i-3]

#include <iostream>
using namespace std;
int main() {
long int n,i;
cin>>n;
while(n--){

long int t;
cin>>t;
if(t==1){
cout<<"0"<<endl;
}
long int dp[t+1]={0};
dp[2]=1;
dp[3]=1;
for(i=4;i<=t;i++)
{
if(i==4)
dp[i]=dp[i-2];
else
dp[i]=(dp[i-2])+(dp[i-3]);
dp[i]=dp[i]%1000000009;
}
cout<<(dp[t])<<endl;
}
return 0;
}


1 Like

You are printing 2 values when t==1. You can just remove that and your code will become correct. Try minimising the number of if conditions. Also, itâ€™s not good practice to have 10^9 + 9 written explicitly, itâ€™s better to put it in a constant variable.

Corrected code
#include <iostream>
using namespace std;
const int p = 1e9 + 9;
int main() {
long int n;
cin>>n;
while(n--){
long int t;
cin>>t;
long int dp[t+1]={0};
dp[2]=1;
dp[3]=1;
for(int i=4;i<=t;i++){
dp[i]=(dp[i-2])+(dp[i-3]);
dp[i]=dp[i]%p;
}
cout<<(dp[t])<<endl;
}
return 0;
}


Also your code isnâ€™t fast enough.

Spoiler

You can precompute the dp and then answer all of them in O(1).
Alternatively you can use matrix exponentiation.
\begin{bmatrix} 1 & 0 & 1\end{bmatrix} \times \begin{bmatrix} 0 & 0 & 1\\ 1 &0 &1\\ 0 & 1 &0 \end{bmatrix}^t. The first term of the resultant matrix will be dp[t]

2 Likes

thank you very much !!
I ll llearn matrix exponentiation
thanks!

while precomputing should i comput it for all 10^6 possible queries
?

Yes.

1 Like

@everule1 How did you come up with that matrix form for the recurrence relation? I also want to learn the technique to convert a recurrence relation into matrix form.

2 Likes

Thanks.