×

Super two letter string - DP Problem

 1 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=mod)dp[i][1]-=mod; } }  return (dp[N][0]+dp[N][1])%mod; answered 19 Mar '18, 14:36 240●1●10 accept rate: 13% Can you please explain the approach ? I mean, can you explain how to identify the states of dynamic programming required here ? (19 Mar '18, 14:47) 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 . (19 Mar '18, 14:56)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,168
×1,657
×643
×398

question asked: 19 Mar '18, 13:49

question was seen: 511 times

last updated: 19 Mar '18, 15:13