区间动态规划例题：字符串交织问题 题目描述 给定三个字符串 s1、s2 和 s3，判断 s3 是否能由 s1 和 s2 的交织组成。交织意味着在保持 s1 和 s2 中字符相对顺序不变的前提下，将 s1 和 s2 的字符交错地合并成一个新字符串。例如，s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 可以交织而成，因为 s3 可以看作是由 s1 和 s2 的字符按顺序交错排列形成的。 解题过程 问题分析 交织操作要求保持 s1 和 s2 各自的字符顺序。我们需要判断是否存在一种方式，将 s1 和 s2 分割成若干子序列（这些子序列在 s3 中连续出现），使得这些子序列按顺序拼接起来恰好等于 s3。由于顺序必须保持，我们可以将问题转化为：逐步匹配 s3 的每个字符，决定它是来自 s1 还是 s2。 状态定义 使用动态规划，定义状态 dp[i][j] 表示 s1 的前 i 个字符（s1[ 0...i-1]）和 s2 的前 j 个字符（s2[ 0...j-1]）是否能交织组成 s3 的前 i+j 个字符（s3[ 0...i+j-1]）。目标是求 dp[len(s1)][len(s2)] 。 状态转移方程 初始状态： dp[0][0] = True （空字符串可以交织成空字符串）。 对于 dp[i][j] ： 如果 i > 0 且 s1[ i-1] == s3[ i+j-1]，则 dp[i][j] 可能由 dp[i-1][j] 转移而来（即当前字符来自 s1）。 如果 j > 0 且 s2[ j-1] == s3[ i+j-1]，则 dp[i][j] 可能由 dp[i][j-1] 转移而来（即当前字符来自 s2）。 因此，转移方程为： dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1]) 。 边界处理 当 i = 0 时，只能从 s2 取字符： dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1] 。 当 j = 0 时，只能从 s1 取字符： dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1] 。 计算顺序 按 i 从 0 到 len(s1)，j 从 0 到 len(s2) 的顺序计算 dp[i][j] ，确保在计算当前状态时，所需的前置状态已计算。 复杂度分析 时间复杂度：O(mn)，其中 m 和 n 分别是 s1 和 s2 的长度。 空间复杂度：O(mn)，可优化至 O(min(m, n))（使用滚动数组）。 示例验证 以 s1 = "aab", s2 = "dbc", s3 = "aadbbc" 为例： 初始化 dp[0][0] = True 。 逐步填充 dp 表，最终 dp[3][3] 为 True，说明 s3 可由 s1 和 s2 交织而成。