题目：

给定三个字符串A, B, C，判断C是否由A和B交错构成。交错构成的意思是，对于字符串C，可以将其每个字符标记为A类或B类，使得我A类的每个字符顺序构成了A字符串，B类的每个字符顺序构成了B字符串。如：对于A=”rabbit” B=”mq”, ”rabmbitq”是由A和B交错构成的，但”rabbqbitm”不是由A和B交错构成。

思路：

【动态规划】

假设dp[i][j]表示A的前i个字符和B的前j个字符是否能够交错构成C的前i+j个字符。

状态转移方程：

dp[i][j]=(dp[i-1][j] && A[i-1]==C[i+j-1]) || (dp[i][j-1] && B[j-1]==C[i+j-1])

含义：

dp[i][j]取决于：

1、A的前i-1个字符和B的前j个字符交错构成C的前i+j-1个字符，且A[i-1]==C[i+j-1]

2、A的前i个字符和B的前j-1个字符交错构成C的前i+j-1个字符，且B[j-1]==C[i+j-1]

初始状态：

dp[0][0]=0;

dp[i][0]=dp[i-1][0] && A[i-1]=C[i-1];　　 (1=<i<=m)

dp[0][j]=dp[0][j-1] && B[j-1]=C[j-1];　　(1=<j<=n)

代码：

#include 
     
      #include 
      
       using namespace std;bool IsCrossString(const string &c,const string &a,const string &b){    int len_c=c.size();    int len_a=a.size();    int len_b=b.size();    if(len_c!=len_a+len_b){        cout<<"Error"<
       
         > dp(len_a+1,vector
        
         (len_b+1));    dp[0][0]=true;    for(int i=1;i<=len_a;i++)        dp[i][0]=dp[i-1][0] && (c[i-1]==a[i-1]);    for(int i=1;i<=len_b;i++)        dp[0][i]=dp[0][i-1] && (c[i-1]==b[i-1]);    for(int i=1;i<=len_a;i++){        for(int j=1;j<=len_b;j++){            dp[i][j]=(dp[i-1][j] && (a[i-1]==c[i+j-1])) || (dp[i][j-1] && (b[j-1]==c[i+j-1]));        }    }/*    for(int i=0;i<=len_a;i++){        for(int j=0;j<=len_b;j++){            cout<< dp[i][j] <<" ";        }        cout<
         
          >a>>b>>c){        cout<< IsCrossString(c,a,b) << endl;    }    return 0;}