区间动态规划例题：最小窗口子序列匹配问题（字符串S中匹配模式P的最小窗口）

题目描述
给定一个字符串 S 和一个模式 P，要求找到 S 中最短的连续子串（窗口），使得该子串包含模式 P 作为子序列（即 P 的字符按顺序出现在子串中，但不要求连续）。若不存在这样的子串，返回空字符串。例如：

• S = "abcdebdde", P = "bde"，最小窗口为 "bcde"（包含子序列 b、d、e）。
• 注意：窗口必须包含 P 的所有字符且顺序一致。

解题思路
此问题可通过动态规划记录匹配状态来解决。核心思想是：

1. 使用二维数组 dp[i][j] 表示匹配 P 的前 j 个字符时，以 S[i] 结尾的最小窗口的起始位置。
2. 通过状态转移逐步匹配字符，最终找到最短窗口。

详细步骤

1. 状态定义
定义 dp[i][j] 表示在 S 的前 i 个字符中匹配 P 的前 j 个字符时，最小窗口的起始下标（即窗口为 [start, i]）。若无法匹配，记为 -1。

2. 初始化

• 当 j = 0 时，匹配空模式，任意位置均可匹配，但窗口长度为0。通常设 dp[i][0] = i（表示空窗口起始于当前位置）。
• 当 j > 0 且未匹配时，初始值为 -1。

3. 状态转移
遍历 i 从 1 到 n（S 的长度），j 从 1 到 m（P 的长度）：

• 若 S[i-1] == P[j-1]（当前字符匹配）：
  • 如果 j == 1，当前字符是模式的首字符，窗口起始位置为 i-1。
  • 否则，窗口起始位置继承自 dp[i-1][j-1]（即前一个字符匹配的状态）。
• 若字符不匹配：
  • 继承 dp[i-1][j] 的起始位置（尝试扩展当前窗口）。

形式化转移方程：

if S[i-1] == P[j-1]:
    if j == 1:
        dp[i][j] = i-1
    else:
        dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = dp[i-1][j]

4. 寻找最小窗口
在所有 dp[i][m] != -1 的位置中，计算窗口长度 i - dp[i][m]，记录最小长度及对应的起始位置。

5. 边界处理

• 若没有有效窗口，返回空字符串。
• 注意字符串索引从0开始，需调整 dp 数组维度为 (n+1) x (m+1)。

举例说明
以 S = "abcdebdde", P = "bde" 为例：

1. 构建 dp 表（简化表示关键值）：
   • 匹配 P[0]='b'：在 S 中第一个 b 在索引1，dp[2][1] = 1。
   • 匹配 P[1]='d'：在 S 中第一个 d 在索引3，但需在 b 之后，因此从 dp[3][1] 继承起始位置1，得到 dp[4][2] = 1。
   • 匹配 P[2]='e'：在索引4的 e 处，继承起始位置1，窗口 [1,4] 长度为4（"bcde"）。
2. 最终比较所有匹配 P 的窗口，最短为 "bcde"。

复杂度分析

• 时间复杂度：O(n·m)，其中 n 和 m 分别为 S 和 P 的长度。
• 空间复杂度：O(n·m)，可优化至 O(m) 通过滚动数组。

通过以上步骤，可系统地找到最小窗口子序列匹配的解。