线性动态规划：交错字符串 题目描述 给定三个字符串 s1 、 s2 和 s3 ，请判断 s3 是否能由 s1 和 s2 交错组成。交错指的是在保持 s1 和 s2 中每个字符相对顺序不变的前提下，将它们穿插合并成一个新字符串。例如： 输入： s1 = "aabcc" , s2 = "dbbca" , s3 = "aadbbcbcac" 输出： true （因为 s3 可以拆分为 "aa" （来自 s1） + "dbbc" （来自 s2） + "bc" （来自 s1） + "a" （来自 s2） + "c" （来自 s1），且各部分顺序不变） 解题思路 问题分析 ：若直接尝试所有交错方式会指数级复杂。动态规划通过记录子问题结果避免重复计算。 状态定义 ：设 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否交错组成 s3 的前 i+j 个字符。 状态转移 ： 若 s1[i-1] == s3[i+j-1] ，则 dp[i][j] 取决于 dp[i-1][j] （即前一步由 s1 提供字符）。 若 s2[j-1] == s3[i+j-1] ，则 dp[i][j] 也取决于 dp[i][j-1] （即前一步由 s2 提供字符）。 综上： dp[i][j] = (dp[i-1][j] && s1[i-1]==s3[i+j-1]) || (dp[i][j-1] && s2[j-1]==s3[i+j-1]) 。 边界条件 ： dp[0][0] = true （空字符串可组成空字符串）。 第一行 dp[0][j] ：仅当 s2 的前 j 字符完全匹配 s3 的前 j 字符时为 true 。 第一列 dp[i][0] ：类似，仅由 s1 匹配 s3 的前 i 字符。 详细步骤 初始化 ：创建 (len(s1)+1) x (len(s2)+1) 的二维数组 dp ，全部初始化为 false 。 处理边界 ： dp[0][0] = true 。 遍历 j 从 1 到 len(s2) ，若 s2[j-1] == s3[j-1] 且 dp[0][j-1] 为真，则 dp[0][j] = true 。 遍历 i 从 1 到 len(s1) ，若 s1[i-1] == s3[i-1] 且 dp[i-1][0] 为真，则 dp[i][0] = true 。 填充动态规划表 ： 双重循环遍历 i 从 1 到 len(s1) ， j 从 1 到 len(s2) ： 计算 k = i+j-1 （ s3 中当前检查的位置）。 若 s1[i-1] == s3[k] 且 dp[i-1][j] 为真，则 dp[i][j] = true 。 否则若 s2[j-1] == s3[k] 且 dp[i][j-1] 为真，则 dp[i][j] = true 。 返回结果 ：最终结果为 dp[len(s1)][len(s2)] 。 示例验证 以 s1="aab" , s2="dbb" , s3="aadbbb" 为例： 初始化后，第一行 dp[0][1] （ s2="d" 匹配 s3="a" ？）为 false ，第一列 dp[1][0] （ s1="a" 匹配 s3="a" ）为 true 。 计算 dp[1][1] ： k=1 ， s1[0]='a' 匹配 s3[1]='a' ？否（实际 s3[1]='a' 但 s1[0] 已用于 dp[1][0] ，需结合位置：此处应比较 s3[i+j-1] 即 s3[1] 与 s1[0] 和 s2[0] ）。 修正： k=i+j-1=1+1-1=1 ， s3[1] 是第二个字符（索引从0开始），即 'a' 。但 s1[0]='a' 匹配，且 dp[0][1] 为假； s2[0]='d' 不匹配，因此 dp[1][1]=false 。 继续填充直至 dp[3][3] ，最终检查是否匹配整个 s3 。 复杂度分析 时间复杂度：O(mn)，其中 m 和 n 分别为 s1 和 s2 的长度。 空间复杂度：可优化至 O(min(m,n))，但基础版本为 O(mn)。