区间动态规划例题：最小窗口子序列问题（字符串匹配最小窗口） 题目描述 给定一个字符串 S 和一个目标字符串 T ，找出 S 中最短的连续子串（窗口），使得 T 是该子串的子序列。如果不存在这样的窗口，返回空字符串。 例如： 输入： S = "abcdebdde" , T = "bde" 输出： "bcde" （最短窗口为 "bcde" ，其中 T 是子序列） 解题思路 问题分析 ： 需要找到 S 中一个子串，使得 T 是其子序列（不必连续，但顺序一致）。 窗口应尽可能短，且包含 T 的所有字符。 关键观察 ： 若固定窗口的起始位置 i ，可贪心匹配 T ：从 i 开始遍历 S ，按顺序匹配 T 的字符，匹配完时记录窗口长度。 但直接枚举所有起点效率低（O(n²)）。需用动态规划优化匹配过程。 动态规划定义 ： 设 dp[i][j] 表示在 S 的前 i 个字符中，匹配到 T 的第 j 个字符时，窗口的起始位置。 状态转移： 若 S[i-1] == T[j-1] ：当前字符匹配，窗口起始点与 dp[i-1][j-1] 相同（即从匹配 T 的前一字符的起点开始）。 若 S[i-1] != T[j-1] ：当前字符不匹配，窗口起始点与 dp[i-1][j] 相同（继承之前的起点）。 初始化： dp[0][0] = 0 ，表示空匹配的起点为0；其他位置初始化为-1（未匹配）。 窗口计算 ： 当 j = len(T) 时，说明 T 已匹配完成，此时窗口长度为 i - dp[i][j] 。 遍历所有 i ，记录最小窗口的起始点和长度。 复杂度优化 ： 使用滚动数组将空间复杂度优化至 O(m)（m 为 T 的长度）。 详细步骤 初始化 dp 数组，长度为 m+1 （m 为 T 的长度）， dp[0] = 0 ，其余为-1。 遍历 S 的每个字符 S[i] （i 从1开始）： 从后往前遍历 T 的字符（避免覆盖状态）： 若 S[i-1] == T[j-1] ，则 dp[j] = dp[j-1] （匹配成功，起点继承上一状态）。 若 j=1 且字符匹配，则 dp[1] = i （匹配 T 的第一个字符时，起点为当前位置）。 当 j = m 且 dp[m] ≠ -1 时，计算窗口长度 i - dp[m] + 1 ，更新最小窗口。 返回最小窗口对应的子串。 举例说明 以 S = "abcdebdde" , T = "bde" 为例： 匹配到 T 的最后一个字符 e 时，窗口起点为 dp[3] （即匹配 b 时的位置），窗口长度为当前位置减起点。 最终找到最短窗口 "bcde" （起点为2，终点为5）。 通过此方法，时间复杂度为 O(n×m)，空间复杂度为 O(m)。