对于两个字符串之间的关系，有很多题目可以用动态规划的思想解答。关键是要找到两个字符串之间的状态转移方程。此处可以使用一个二维矩阵，找出两个字符串的前缀之间的关系，从而推出两个字符串之间的关系。
下面以LeetCode上面Interleaving String为例。
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
例如s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"，结果为True，而s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"，结果为False。
我们采用bool型二维数组interleave，interleave[i][j]代表s1的前i个字符与s2的前j个字符进行插入操作，能否得到s3的前i+j个字符。我们考虑以下几个情况：
- 如果
interleave[i-1][j]和interleave[i][j-1]都为False，说明无论是s1的第i个字符还是s2的第j个字符都无法作为s3的末尾字符，此时interleave[i][j]必然为False。 - 除此之外，如果
interleave[i-1][j] == True，说明s1[:i-1]能插入s2[:j]中得到s3[:i-1+j]。如果s1第i个字符等于s3的第i+j个字符，则interleave[i][j] = True。 - 除此之外，则
interleave[i][j-1]必然True，说明s1[:i]能插入s2[:j-1]中得到s3[:i-1+j]。如果s2第j个字符等于s3的第i+j个字符，则interleave[i][j] = True。
我们可以得到状态转移方程如下
$$
interleave[i][j] =
\begin{cases}
False \quad & interleave[i-1][j] == False \wedge \\ \quad & interleave[i][j-1] == False \\
s2[j-1] == s3[i+j-1] \quad & interleave[i][j-1] == True \\
s1[i-1] == s3[i+j-1] \quad & otherwise
\end{cases}
$$
对于边界条件，例如interleave[i][0]即代表着s1[:i]是否为s3[:i],则interleave[i][0] = interleave[i-1][0] and s1[i-1] == s3[i-1],同理interleave[0][i] = interleave[0][i-1] and s2[i-1] == s3[i-1]。最终interleave[len(s1)][len(s2)]即为所求。
原题例一的状态转移矩阵如下所示。
