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;
}
I haven’t read the question, but I have never seen the answer asked modulo 10^9 + 9. You should post the question link when asking a doubt.
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
?
@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.