交错字符串如何用动态规划判断？二维状态为什么对应两个字符串的前缀长度？

简化版

交错字符串用 dp[i][j] 表示 s1 前 i 个字符和 s2 前 j 个字符，能否交错组成 s3 前 i+j 个字符。当前字符要么来自 s1[i-1]，要么来自 s2[j-1]，只要有一种来源匹配并且前一个状态可行即可。

详细版

先判断长度：s1.length() + s2.length() 必须等于 s3.length()。然后填二维布尔表。转移为：如果 s1[i-1] == s3[i+j-1] 且 dp[i-1][j] 为真，则当前可行；如果 s2[j-1] == s3[i+j-1] 且 dp[i][j-1] 为真，也可行。

第一行表示只用 s2 匹配，第一列表示只用 s1 匹配。时间复杂度 O(mn)，空间复杂度可以优化到 O(n)。

完整版教学

一、交错的含义是保序合并

交错字符串不是随便打乱字符，而是把 s1 和 s2 保持各自相对顺序地合并成 s3。例如 s1="ab"，s2="cd"，"acbd" 合法，因为 a 在 b 前，c 在 d 前。

s1: a   b
s2:   c   d
s3: a c b d

如果 s3="adbc"，虽然字符集合一样，但 s2 中 d 跑到了 c 前面，所以不合法。

二、为什么状态要用两个前缀长度

交错过程里，我们需要知道 s1 用了多少字符、s2 用了多少字符。只知道 s3 的位置不够，因为同一个位置可能由不同的分配方式到达。

定义：

dp[i][j] = s1 前 i 个字符和 s2 前 j 个字符，能否组成 s3 前 i+j 个字符

这个定义让 s3 的位置自动确定为 i+j-1，不需要第三维。

维度	表示
`i`	已使用 s1 的字符数
`j`	已使用 s2 的字符数
`i+j`	已组成 s3 的字符数

三、当前字符可能来自哪里

要组成 s3[i+j-1]，最后一个字符有两种来源：

来自 s1：s1[i-1] == s3[i+j-1] 且 dp[i-1][j]
来自 s2：s2[j-1] == s3[i+j-1] 且 dp[i][j-1]

因此：

dp[i][j] =
  (i > 0 && dp[i-1][j] && s1[i-1] == s3[i+j-1])
  ||
  (j > 0 && dp[i][j-1] && s2[j-1] == s3[i+j-1])

记忆钩子：交错字符串每一步只问“s3 当前最后一个字符，是从 s1 拿的，还是从 s2 拿的”。

四、用具体例子走表

设：

s1 = "ab"
s2 = "cd"
s3 = "acbd"

状态路径可以是：

dp[0][0] = true
dp[1][0] = true  // a 来自 s1
dp[1][1] = true  // c 来自 s2
dp[2][1] = true  // b 来自 s1
dp[2][2] = true  // d 来自 s2

如果某一步两个来源都匹配失败，那个状态就是 false。布尔 DP 表示的是可达性，而不是方案数。

五、边界初始化怎么处理

第一列表示 s2 一个字符都不用，只靠 s1 去匹配 s3：

dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1]

第一行同理：

dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1]

只要中间某个字符不匹配，后面就都无法继续只靠单个字符串匹配。

六、代码模板和复杂度

boolean isInterleave(String s1, String s2, String s3) {
    int m = s1.length(), n = s2.length();
    if (m + n != s3.length()) return false;
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            int k = i + j - 1;
            if (i > 0) {
                dp[i][j] |= dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(k);
            }
            if (j > 0) {
                dp[i][j] |= dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(k);
            }
        }
    }
    return dp[m][n];
}

注意 i=0,j=0 时 k=-1，但两个 if 都不会进入，所以安全。也可以单独初始化第一行第一列，让主循环从 1 开始。

七、常见误区与追问

误区：只比较字符数量。 字符数量相同不代表保序合并合法。
误区：忘记先判断长度。 长度不等时一定无法交错组成。
误区：把 s3 下标写成 i+j。 当前最后一个字符下标是 i+j-1。
追问：能不能 DFS 记忆化？ 可以，状态同样是 (i,j)，本质和 DP 表一致。
追问：空间能优化吗？ 可以用一维 dp[j]，因为每个状态只依赖上方和左方。
追问：如果要求方案数怎么办？ 把布尔值改成计数，相同来源时累加方案数。

八、加强记忆

交错字符串的核心是“两个前缀拼一个前缀”。dp[i][j] 代表 s1 用了 i 个、s2 用了 j 个，于是 s3 必然用了 i+j 个。最后一个字符不是来自 s1 就是来自 s2，匹配字符并且前一状态可达即可。先判长度，再填布尔表，这题就很稳。

简化版

详细版