算法描述：
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false
解题思路：动态规划题。s3中的字符要么与s1中的字符相同，要么与s2中的字符相同。
递推式：
dp[i][j] = (dp[i-1][j] && (s3[i+j-1]==s1[i-1]) || dp[i][j-1] && (s3[i+j-1]==s2[j-1]))
bool isInterleave(string s1, string s2, string s3) { if(s1.size()+s2.size()!=s3.size()) return false; vector<vector<bool>> dp(s1.size()+1, vector<bool>(s2.size()+1,false)); dp[0][0] =true; for(int i=1; i <= s1.size(); i++) { dp[i][0] = dp[i-1][0] && (s1[i-1]==s3[i-1]); } for(int j=1; j <= s2.size(); j++){ dp[0][j] = dp[0][j-1] && (s2[j-1]==s3[j-1]); } for(int i=1; i <=s1.size(); i++){ for(int j=1; j <=s2.size(); j++){ dp[i][j] = (dp[i-1][j] && (s3[i+j-1]==s1[i-1])) || (dp[i][j-1] && (s3[i+j-1]==s2[j-1])); } } return dp[s1.size()][s2.size()]; }
LeetCode-97-Interleaving String
原文：https://www.cnblogs.com/nobodywang/p/10385007.html