**一. 題目描述** Given s1; s2; s3, find whether s3 is formed by the interleaving of s1 and s2.? For example, Given: s1 = “aabcc”, s2 = “dbbca”,? When s3 = “aadbbcbcac”, return true.? When s3 = “aadbbbaccc”, return false. **二. 題目分析** 此題可使用二維動態規劃來解決，下表給出了直觀的匹配過程：  設某一格的狀態為`k[i][j]`，表示`s1[i]`或`s2[j]`，與`s3[i+j]`的匹配結果。`s3`可與`s1`和`s2`相匹配時，可分為以下兩種情況： 如果`s1`?的最后一個字符等于`s3`?的最后一個字符，則`k[i][j]=k[i-1][j]`；? 如果`s2`?的最后一個字符等于`s3`?的最后一個字符，則`k[i][j]=k[i][j-1]`。 因此狀態轉移方程如下：? `f[i][j] = (s1[i - 1] == s3 [i + j - 1] && f[i - 1][j]) || (s2[j - 1] == s3 [i + j - 1] && f[i][j - 1]);` **三. 示例代碼** ~~~ #include <iostream> #include <string> #include <vector> using namespace std; class Solution { public: bool isInterleave(string s1, string s2, string s3) { if (s3.size() != s1.size() + s2.size()) return false; if (s3[0] != s1[0] && s3[0] != s2[0]) return false; vector<vector<bool> > k(s1.size() + 1, vector<bool>(s2.size() + 1, false)); k[0][0] = true; // 邊界設置 for (size_t i = 1; i <= s1.size(); ++i) k[i][0] = (s1[i - 1] == s3[i - 1]) && k[i - 1][0]; for (size_t j = 1; j <= s2.size(); ++j) k[0][j] = (s2[j - 1] == s3[j - 1]) && k[0][j - 1]; for (size_t i = 1; i <= s1.size(); ++i) { for (size_t j = 1; j <= s2.size(); ++j) { k[i][j] = ((s1[i - 1] == s3[i + j - 1]) && k[i - 1][j]) || ((s2[j - 1] == s3[i + j - 1]) && k[i][j - 1]); } } return k[s1.size()][s2.size()]; } }; ~~~   **四. 小結** 編程時要注意邊界條件的問題和數組的下標問題。