## 題目描述 輸入三個字符串s1、s2和s3，判斷第三個字符串s3是否由前兩個字符串s1和s2交錯而成，即不改變s1和s2中各個字符原有的相對順序，例如當s1 = “aabcc”，s2 = “dbbca”，s3 = “aadbbcbcac”時，則輸出true，但如果s3=“accabdbbca”，則輸出false。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.04.md#分析與解法)分析與解法 此題不能簡單的排序，因為一旦排序，便改變了s1或s2中各個字符原始的相對順序，既然不能排序，咱們可以考慮下用動態規劃的方法，令dp[i][j]代表s3[0...i+j-1]是否由s1[0...i-1]和s2[0...j-1]的字符組成 * 如果s1當前字符（即s1[i-1]）等于s3當前字符（即s3[i+j-1]），而且dp[i-1][j]為真，那么可以取s1當前字符而忽略s2的情況，dp[i][j]返回真； * 如果s2當前字符等于s3當前字符，并且dp[i][j-1]為真，那么可以取s2而忽略s1的情況，dp[i][j]返回真，其它情況，dp[i][j]返回假 參考代碼如下： ~~~ public boolean IsInterleave(String s1, String 2, String 3){ int n = s1.length(), m = s2.length(), s = s3.length(); //如果長度不一致，則s3不可能由s1和s2交錯組成 if (n + m != s) return false; boolean[][]dp = new boolean[n + 1][m + 1]; //在初始化邊界時，我們認為空串可以由空串組成，因此dp[0][0]賦值為true。 dp[0][0] = true; for (int i = 0; i < n + 1; i++){ for (int j = 0; j < m + 1; j++){ if ( dp[i][j] || (i - 1 >= 0 && dp[i - 1][j] == true && //取s1字符 s1.charAT(i - 1) == s3.charAT(i + j - 1)) || (j - 1 >= 0 && dp[i][j - 1] == true && //取s2字符 s2.charAT(j - 1) == s3.charAT(i + j - 1)) ) dp[i][j] = true; else dp[i][j] = false; } } return dp[n][m] } ~~~ 理解本題及上段代碼，對真正理解動態規劃有一定幫助。