转化为二维地图游走问题。
比如s1="abab"，s2="aab"，s3="aabaabb"，则有如下地图，其中"^"表示开始位置，"$"表示终止位置。
a a b <- s2
s1 -> a ^ . .
b . . .
a . . .
b . . $
现在问题变成了，能否走出一条等于s3的路径？
对于地图上的任意一点，不妨设坐标为(i, j)，令k为当前坐标下s3对应的位置。
如果s1[i]=s3[k]则可以向下走
如果s2[j]=s3[k]则可以向右走
否则意味着无路可走了
令res[i][j]表示s1[i..s1.length-1]和s2[j..s2.length-1]能否组成s3[k..s3.length]，其中s3.length-k=(s1.length-i) + (s2.length-j)
则有递推公式：res[i][j] = (s1[i]等于s3[k]，且 res[i+1][j]) 或 (s2[j]等于s3[k]，且res[i][j+1])
由于计算res[i][j]时只用到了res[i+1][j]或res[i][j+1]（相邻层），所以在具体编码实现的时候可以进行状态压缩，用一维数组保存res[i][j]
代码：
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
vector<bool> res(len2 + , false);
if (len1 + len2 != len3) return false;
if (!len1) return s2 == s3;
if (!len2) return s1 == s3;
res[len2] = true;
for (int j = len2 - ; j >= ; j--)
res[j] = s3[len3 - (len2 - j)] == s2[j] && res[j + ];
for (int i = len1 - ; i >= ; i--) {
for (int j = len2 - ; j >= ; j--) {
int k = len3 - (len1 - i) - (len2 - j);
res[j] = (s3[k] == s1[i] && res[j]) || (s3[k] == s2[j] && res[j + ]);
}
}
return res[];
}