Super two letter string - DP Problem

general
, , ,
1

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

link to the problem : https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/super-two-letter-strings/description/

2

Let dp[i][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][0]=1 and dp[1][1]=0;

//calculating for length>1

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

	dp[i][0]=dp[i][1]=0;// initializing to 0;

	dp[i][0]=(dp[i-1][1]+dp[i-1][0])%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[i][1]+=(dp[i-j][0]);

	   if(dp[i][1]>=mod)dp[i][1]-=mod;
	}
}

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

1 Like
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 .