学步园

TAG   动态规划 dp

使3个字符串A B C

dp[i][j]表示A的前i个字符和B的前j个字符能否组合成C的前i+j个字符

状态转移方程：

 dp[i][j]=    dp[i-1][j] && C[i+j-1]==A[i-1]    ||      dp[i][j-1] && C[i+j-1]==B[j-1];  //注意边界

/* source code of submission 419888, Zhongshan University Online Judge System */<br /> #include <stdio.h><br /> #include <memory.h><br /> #include <string.h><br /> bool dp[201][201];<br /> char A[201],B[201],C[401];<br /> int T,n;<br /> int len;<br /> int main(int argc, char *argv[])<br /> {<br /> scanf("%d", &T);<br /> n=0;<br /> while ( n<T )<br /> {<br /> scanf("%s%s%s", A, B, C);<br /> memset(dp, false, sizeof(dp) );<br /> dp[0][0]=true;<br /> len=strlen(A);<br /> for (int i=0; i<=len; ++i)<br /> {<br /> for (int j=0; j<=len; ++j)<br /> {<br /> if ( i+j==0 )<br /> {<br /> continue;<br /> }<br /> if ( i==0 )<br /> {<br /> dp[0][j]=dp[0][j-1] && C[j-1]==B[j-1];<br /> }<br /> else if ( j==0 )<br /> {<br /> dp[i][0]=dp[i-1][0] && C[i-1]==A[i-1];<br /> }<br /> else<br /> {<br /> dp[i][j]= dp[i-1][j] && C[i+j-1]==A[i-1]<br /> || dp[i][j-1] && C[i+j-1]==B[j-1];<br /> }<br /> //printf("%d", dp[i][j]);</p> <p> }<br /> //printf("/n");<br /> }<br /> printf("Data set %d: %s/n",++n, dp[len][len]? "yes": "no" );<br /> }<br /> return 0;