区间动态规划例题：最小窗口子序列问题（字符串匹配最小窗口） 题目描述 给定一个字符串 S 和一个字符串 T ，找出 S 中包含 T 所有字符的最短连续子串（窗口），并返回该子串。如果不存在这样的子串，返回空字符串。要求时间复杂度尽可能低。 示例 输入： S = "abcdebdde" , T = "bde" 输出： "bcde" （最短匹配窗口为 "bcde" ，而非 "bdde" ，因为前者更短） 解题思路 本题是区间动态规划的变种，核心思想是通过动态规划记录匹配状态，逐步缩小窗口范围。具体步骤如下： 状态定义 定义 dp[i][j] 表示在 S 的前 i 个字符中匹配 T 的前 j 个字符时， 匹配窗口的起始下标 （即最短子串的起始位置）。 若无法匹配，则 dp[i][j] = -1 。 状态转移 当 S[i-1] == T[j-1] 时： 若 j == 1 （匹配 T 的第一个字符），则窗口起始位置为 i-1 （当前字符）。 否则，窗口起始位置继承自 dp[i-1][j-1] （即前一个字符的匹配状态）。 当 S[i-1] != T[j-1] 时： 继承 dp[i-1][j] 的起始位置（尝试延长当前窗口）。 转移方程： \[ dp[ i][ j ] = \begin{cases} i-1 & \text{if } j=1 \text{ and } S[ i-1]=T[ j-1 ] \\ dp[ i-1][ j-1] & \text{if } j>1 \text{ and } S[ i-1]=T[ j-1 ] \\ dp[ i-1][ j] & \text{if } S[ i-1] \neq T[ j-1 ] \end{cases} \] 记录最短窗口 遍历过程中，当 j == len(T) 且 dp[i][j] != -1 时，计算当前窗口长度 i - dp[i][j] ，并更新最短窗口的起始位置和长度。 边界处理 初始化 dp[i][j] = -1 表示未匹配。 注意字符串下标从0开始。 逐步推导示例 以 S = "abcdebdde" , T = "bde" 为例： 初始化 DP 表 （大小为 (len(S)+1) x (len(T)+1) ），全部填 -1。 填充过程 （只列关键步骤）： i=2 （ S[1]='b' ），匹配 T[0]='b' ： dp[2][1] = 1 （窗口起始下标为1）。 i=5 （ S[4]='e' ），匹配 T[2]='e' ： 需先匹配 T[0:2]="bd" ，发现 i=4 时 dp[4][2] 由 dp[3][1] 继承而来（ S[2]='c' 未直接匹配，略过中间步骤），最终得到窗口起始下标为1，长度为 5-1=4 ，即 "bcde" 。 i=9 时匹配到另一个窗口 "bdde" ，长度为4，但起始下标更大（5），因此最短窗口仍是 "bcde" 。 最终结果 ：起始下标=1，长度为4，子串为 "bcde" 。 算法优化 实际代码中可压缩 DP 数组为一维，节省空间。 遍历时仅需维护当前行和上一行的状态。 复杂度分析 时间复杂度：O(len(S) * len(T)) 空间复杂度：O(len(T))（压缩后） 通过此方法，可高效找到最短匹配窗口，适用于字符串匹配类问题。