本文主要是介绍动态规划-leetcode#97-交错字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
class Solution {
public:bool isInterleave(string s1, string s2, string s3) {if(s1.length()+s2.length()!=s3.length()) return false;vector<vector<bool>> dp(s1.length()+1,vector<bool>(s2.length()+1,false));dp[0][0]=true;//s1空，s2空，可以组成s3空for(int i=0;i<=s1.length();i++){for(int j=0;j<=s2.length();j++){int id = i+j-1;if(i>=1 && s1[i-1]==s3[id] && dp[i-1][j]) dp[i][j]=true; if(j>=1 && s2[j-1]==s3[id] && dp[i][j-1]) dp[i][j]=true; }}return dp[s1.length()][s2.length()];}
};题意解析：s1和s2交错拼接，是否可以拼成s3，这里需要注意的是s1和s2必须是顺次访问的，不能跳着取字符去拼接，就是每次都要从剩余的字符串的头部还是取。举例aabcc和dbbca是否能拼成aadbbbaccc，dp[i][j] 表示s1的前i个与s2的前j个是否可以拼成s3的前i+j个，那么就有两种情况，要么最后一个字符来自s1，要么来自s2，如果s3的前i+j个字符的最后一个字符s3[i+j-1]来自s1，也就是s3[i+j-1]和s1[i-1]相等，那么只要dp[i-1][j]是true，dp[i][j]就是true；如果s3的前i+j个字符的最后一个字符s3[i+j-1]来自s2，也就是s3[i+j-1]和s2[j-1]相等，那么只要dp[i][j-1]是true，dp[i][j]就是true。
初始时候，s1=空串，s2=空串，组成的s3也是空串，dp[0][0]=true;这里的循环i和j表示的是前i个字符和前j个字符，当比较字符是否相等时，索引为i-1，j-1，i+j-1。
这篇关于动态规划-leetcode#97-交错字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
