区间动态规划例题：字符串交织问题 题目描述 给定三个字符串 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），且各部分顺序与原字符串一致） 解题思路 问题分析 若 s3 的长度不等于 s1 与 s2 长度之和，直接返回 false 。 交织过程需保证 s1 和 s2 的字符在 s3 中按原顺序出现，但可以交替穿插。 定义状态 设 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否交织成 s3 的前 i+j 个字符。 状态维度： (len(s1)+1) × (len(s2)+1) 。 状态转移方程 初始状态： dp[0][0] = true （空字符串可以交织成空字符串）。 对于 dp[i][j] ： 若 s1[i-1] == s3[i+j-1] ，则检查 dp[i-1][j] （即当前字符来自 s1 ）。 若 s2[j-1] == s3[i+j-1] ，则检查 dp[i][j-1] （即当前字符来自 s2 ）。 转移方程： 边界处理 第一行（ i=0 ）：仅由 s2 的前 j 个字符与 s3 匹配，需满足 s2[0:j] == s3[0:j] 。 第一列（ j=0 ）：仅由 s1 的前 i 个字符与 s3 匹配，需满足 s1[0:i] == s3[0:i] 。 逐步推导示例 以 s1 = "aabcc" , s2 = "dbbca" , s3 = "aadbbcbcac" 为例： 初始化 dp 表（6×6）， dp[0][0] = true 。 填充第一行和第一列： 第一行： dp[0][j] = (s2[j-1] == s3[j-1] && dp[0][j-1]) 第一列： dp[i][0] = (s1[i-1] == s3[i-1] && dp[i-1][0]) 按行遍历填充： 例如 dp[1][1] ： s1[0] = 'a' 匹配 s3[1] = 'a' ，检查 dp[0][1] （需提前计算）； s2[0] = 'd' 不匹配 s3[1] ，故结果取决于 dp[0][1] 。 逐步推导至 dp[5][5] ，最终结果为 true 。 复杂度分析 时间复杂度：O(m×n)，其中 m 和 n 分别为 s1 和 s2 的长度。 空间复杂度：可优化至 O(min(m, n))，仅保留当前行和上一行的状态。 关键点 状态定义需明确“前 i/j 个字符”与 s3 的前 i+j 个字符的匹配关系。 边界条件需单独处理，避免越界错误。 通过示例手动推导可验证转移逻辑的正确性。