区间动态规划例题：最小窗口子序列问题 题目描述 给定字符串 S 和 T，找出 S 中最短的子串（连续子序列），使得 T 是该子串的子序列。如果不存在这样的子串，返回空字符串。如果有多个长度相同的最短子串，返回最左边的一个。 示例 S = "abcdebdde", T = "bde" 答案："bcde"（包含子序列 "bde"，且比 "bdde" 更短） 解题思路 这个问题可以通过区间动态规划解决，但更高效的方法是使用双指针或动态规划记录匹配位置。我将采用基于动态规划的"最后出现位置"方法，它本质上是区间DP思想的变种。 详细解题步骤 步骤1：定义状态 定义 dp[ i][ j ] 表示在 S 的前 i 个字符中匹配 T 的前 j 个字符时，匹配序列的起始位置。 更准确地说，dp[ i][ j] 表示使得 S[ k:i] 包含 T[ 1:j ] 作为子序列的最大起始位置 k。 步骤2：状态转移方程 当 S[ i] = T[ j ] 时： 如果 j = 1，那么匹配可以从位置 i 开始，即 dp[ i][ 1 ] = i 如果 j > 1，那么我们需要在 i 之前找到匹配 T[ 1:j-1] 的位置，即 dp[ i][ j] = dp[ i-1][ j-1 ] 当 S[ i] ≠ T[ j ] 时： 当前字符不匹配，起始位置继承自前一个位置，即 dp[ i][ j] = dp[ i-1][ j ] 步骤3：初始化 dp[ 0][ j ] = -1（空字符串无法匹配非空T） dp[ i][ 0 ] = i（匹配空字符串的起始位置为i） 步骤4：寻找最优解 遍历整个S字符串，当匹配完成时（j = len(T)），计算当前窗口长度： 窗口长度 = i - dp[ i][ len(T) ] + 1 记录最小窗口及其起始位置。 具体执行过程 以 S = "abcdebdde", T = "bde" 为例： 初始化dp表（i从1开始，j从1开始）： 第一行和第一列按规则初始化 逐个填充dp表： i=1, j=1: S[ 1]='a'≠'b', dp[ 1][ 1]=dp[ 0][ 1 ]=-1 i=2, j=1: S[ 2]='b'='b', dp[ 2][ 1 ]=2 i=3, j=2: S[ 3]='c'≠'d', dp[ 3][ 2]=dp[ 2][ 2 ]=-1 ... 当匹配完成时记录窗口 最终找到最小窗口为"bcde"（起始位置2，长度4） 算法优化 实际实现时可以使用滚动数组优化空间复杂度，从O(mn)降到O(n)。 复杂度分析 时间复杂度：O(mn)，其中m为T长度，n为S长度 空间复杂度：O(n)（优化后） 这种方法确保了找到最短且最左边的满足条件的子串，是区间动态规划在字符串匹配中的典型应用。