 # Super two letter string - DP Problem

#1

Please help me with this DP problem. There is NO editorial for this…please help…thanks

#2

Let dp*[j] be the number of number of two letter strings which satisfy the given constraints which are of length i and last character is j. if(j==0) the last character is Y , if (j==1) the last character is X;

Now base case is dp=1 and dp=0;

//calculating for length>1

``````           for(int i=2;i<=N;i++){

dp*=dp*=0;// initializing to 0;

dp*=(dp[i-1]+dp[i-1])%mod;
//for 'Y' the previous can be anything so adding those values

for(int j=1;j<P;j++){

if(i-j<=0)break;

dp*+=(dp[i-j]);

if(dp*>=mod)dp*-=mod;
}
}
``````

return (dp[N]+dp[N])%mod;

#3

Can you please explain the approach ? I mean, can you explain how to identify the states of dynamic programming required here ?

#4

The states here are length of the string and last character used for the length, length can go upto N and last character is either X or Y, so two states one is of length N and other of 2. Now to fill the table I have commented in the code .