題目
題意：
給你三個字元串s1，s2，s3 問你s3是否由s1和s2互相交叉組成。也就是說s3中的某個子序列是s1，剩下的字元串組成s2。
第一眼感覺是最長公共子序列，一開始的想法是先把s3和s1求最長公共子序列,然後從s3的部分中把s1摳出來，在再和s2求最長公共子序列。
但是這種做法很麻煩，而且是錯誤的。
正确的思路和最長公共子序列有點相似。
dp[i][j][k] = 1 表示從0-i 的s3區間是由 0-j的s1區間和0-k的s2區間組合而來的。
狀态轉移方程也很簡單。
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int dp[s3.size()+1][s1.size()+1][s2.size()+1];
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
for(int i=1;i<=s3.size();i++)
{
for(int j=0;j<=s1.size();j++)
{
for(int k=0;k<=s2.size();k++)
{
if(j!=0 && s3[i-1]==s1[j-1]) {
if (dp[i-1][j-1][k]==1)
dp[i][j][k] = 1;
}
if(k!=0 && s3[i-1]==s2[k-1])
{
if(dp[i-1][j][k-1]==1)
dp[i][j][k]=1;
}
}
}
}
if(dp[s3.size()][s1.size()][s2.size()]==1)
return true;
else
return false;
}
}; 複制