区间动态规划例题：最小窗口子序列问题 题目描述 给定一个字符串 S 和一个字符串 T ，在 S 中寻找一个最短的连续子串，使得子串包含 T 的所有字符（按顺序出现，但允许中间插入其他字符）。例如： S = "abcdebdde" , T = "bde" ，答案应为 "bcde" （长度 4），因为它是包含 T 顺序的最短窗口。 要求时间复杂度尽量优化，通常 |S| 和 |T| 可能较大。 解题思路 问题分析 需要找到 S 中满足条件的最短子串，且 T 必须是该子串的 子序列 （顺序匹配，不要求连续）。 暴力法：枚举所有子串，检查是否包含 T 作为子序列，复杂度 O(|S|²·|T|)，不可接受。 动态规划定义 设 dp[i][j] 表示：在 S 的前 i 个字符中，匹配 T 的前 j 个字符时， 匹配起始位置的最大下标 （即匹配序列的起点索引）。 另一种常见定义： dp[i][j] 表示以 S[i] 结尾的、包含 T[0..j] 作为子序列的最小窗口长度。但这里采用起点追踪法更直观。 状态转移方程 初始化： dp[i][0] = i （空串匹配任意起点为当前下标）。 若 S[i-1] == T[j-1] ： 当前字符匹配，则 dp[i][j] = dp[i-1][j-1] （继承上次匹配的起点）。 若 S[i-1] != T[j-1] ： 当前字符不匹配，则 dp[i][j] = dp[i-1][j] （起点不变，继续在 S 中前移）。 转移后，若 j == |T| ，说明匹配完成，计算窗口长度 i - dp[i][j] ，更新最小值。 优化空间 dp[i][j] 只依赖上一行，可压缩为一维数组，倒序更新 j 。 详细步骤 初始化 dp[0..|S|][0] = 0,1,2,... （匹配空串时起点为当前下标）。 遍历 i 从 1 到 |S|， j 从 |T| 到 1（倒序避免覆盖）： 若 S[i-1] == T[j-1] ，则 dp[j] = dp[j-1] （ j=1 时起点为 i-1 ）。 若 j == |T| ，检查窗口长度 i - dp[j] ，更新最短窗口的起点和长度。 最终输出最短窗口子串。 示例演算 S = "abcdebdde" , T = "bde" 初始化 dp = [0, -1, -1] （ -1 表示未匹配）。 i=1 （S[ 0]='a'）：不匹配 T[ 0]='b'， dp 不变。 i=2 （S[ 1]='b'）：匹配 T[ 0]，更新 dp[1] = 1 ；继续检查 j=2,3 无变化。 i=3 （S[ 2]='c'）：不匹配 T[ 1]='d'， dp[2] 仍为 -1。 i=4 （S[ 3]='d'）：匹配 T[ 1]，更新 dp[2] = dp[1] = 1 ；匹配完成时窗口长度 4-1=3 （"bcd"）。 继续遍历找到更优解 i=7 时窗口 "bcdebd" 长度 6，但 i=9 时得到 "bdde" 长度 4 为最优。 关键点 通过 dp[j] 记录匹配到 T 第 j 个字符时的起点，避免重复扫描。 倒序更新 j 确保不会覆盖当前行未使用的旧值。 时间复杂度 O(|S|·|T|)，空间 O(|T|)。 这种方法高效地解决了最短窗口子序列问题，适用于大规模字符串匹配场景。