Interleaving String

  res[i][j] means whether the first i characters of s1 and the first j characters of s2 can construct the first i+j characters of s3.
if the incoming char of s1 is used to match the incoming char of s3, res[i][j]=res[i-1][j]&&s1[i-1]==s3[i+j-1] 
if the incoming char of s2 is used to match the incoming char of s3, res[i][j]=res[i][j-1]&&s2[j-1]==s3[i+j-1] 
base cases are res[0][0], res[0][j], res[i][0]

可以看出递推式中只需要用到上一行的信息，所以我们只需要一个一维数组就可以完成历史信息的维护
  bool isInterleave(string s1, string s2, string s3) {
        int m=s1.length();
        int n=s2.length();
        int p=s3.length();
        if(m+n!=p) return false;
        vector<bool> res(n+1,false);
        res[0]=true;//base case:res[0][0]
        for(int j=1;j<=n;j++)//base case:res[0][j]
            res[j]=res[j-1]&&s2[j-1]==s3[j-1];
        for(int i=1;i<=m;++i){
            res[0]=res[0]&&s1[i-1]==s3[i-1];//base case:res[i][0]
            for(int j=1;j<=n;++j){
                res[j]=res[j]&&s1[i-1]==s3[i+j-1] || res[j-1]&&s2[j-1]==s3[i+j-1];
            }
        }
        return res[n];   
    }