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;
}

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.


Here is the problem link
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.