区间动态规划例题：最小窗口子序列匹配问题（字符串S中匹配模式P的最小窗口）
题目描述
给定一个字符串 S 和一个模式串 P，要求找出 S 中包含 P 作为子序列的最短连续子串（即最小窗口子序列）。如果有多个满足条件的窗口，返回任意一个的起始和结束索引（或长度）。如果不存在这样的窗口，返回空结果。
例如：
- S = "abcdebdde", P = "bde"
最短窗口是 "bcde" 包含子序列 "bde"，但更优的是 "bdde"（更短）。正确输出可以是起始索引 4，结束索引 6（"bdde" 的子序列 "bde"）。
解题思路
这个问题可以用动态规划（DP）解决，但更常见的优化解法是双指针或预处理+贪心。不过，区间DP的思路也可以帮助理解状态设计。我们下面讲一种结合预处理和动态规划的高效方法。
步骤 1：问题分析
- 我们需要在 S 中找到一段连续子串 S[i:j]，使得 P 是这个子串的子序列。
- 子序列不要求连续，但顺序必须一致。
- 要求连续子串长度最小。
直接枚举所有子串并检查子序列会超时（O(|S|²|P|)），需要优化。
步骤 2：预处理 next 数组
定义 next[i][ch]：表示在 S 的位置 i 及之后，字符 ch 第一次出现的位置。
这样可以快速跳转到下一个匹配字符。
预处理方法（从后往前递推）：
- 初始化 next[|S|][*] = -1（不存在）。
- 从 |S|-1 到 0：
- 对于每个字符 ch，next[i][ch] = i（如果 S[i] == ch），否则 next[i][ch] = next[i+1][ch]。
但这里我们更常用的是另一种形式：
定义 next_pos[i][ch]：在 i 的右侧（包括 i）字符 ch 下一次出现的位置。
实际常用的是：
- 先建立每个字符的出现位置列表。
- 然后对每个 i，用二分查找找下一个 ch 的位置。
但更简单的实现是直接预处理一个数组：
next[i][ch] = 从 i 开始（含 i）下一个 ch 的位置，若没有则是 ∞。
步骤 3：动态规划定义
另一种区间DP思路（虽然不是严格区间合并，但是区间上的递推）：
定义 dp[i][k]：在 S 中从位置 i 开始匹配 P 的前 k 个字符，需要到达的最小位置（即匹配完 P 的前 k 个字符后的结束位置+1？）
但更常见的定义是：
dp[i][k] = 匹配 P 的前 k 个字符，且匹配从 S 的 i 位置开始，匹配结束的最小右边界+1。
其实更直观的是：
设 f[i][k] = 在 S[i:] 中匹配 P[k:] 作为子序列时，所需的最短子串的右边界（即匹配完 P[k:] 后的结束索引+1）。
但这样复杂度高。
实际上更高效且简单的解法（非区间DP，但可看作线性DP+贪心）：
定义：
start[i] = 为了匹配 P[0:i] 作为子序列，且以某个位置结束，其起始位置尽可能靠左？不，我们反过来：
我们找所有可能的结束位置 j，然后找对应的最大起始位置 i，使得 S[i:j+1] 包含 P。
方法：
- 预处理一个数组 last[j][ch]：在 j 之前（含 j）字符 ch 最后一次出现的位置。
- 但更妙的是：从后往前匹配 P，找到最短窗口。
步骤 4：标准解法（非区间DP，但是动态规划思想）
我们用一个数组 dp[k] 表示匹配 P 的前 k 个字符时，在 S 中的起始位置 i 对应的最短窗口的结束位置。
但更常见的做法（二分法或双指针）：
- 对每个起始位置 i，贪心匹配 P，得到最小的 j，使得 S[i:j+1] 包含 P。
- 取所有 (i, j) 中长度最小的。
贪心匹配方法：
对于给定的 i，用指针 p=0，从 i 开始遍历 S，如果 S[q] == P[p]，则 p++，当 p == |P| 时，就找到了一个结束位置 j=q。
然后让 i 增加 1，重复。这样是 O(|S|²) 最坏。
优化：
预处理 next_pos[i][ch]：在 i 及之后字符 ch 第一次出现的位置。
然后匹配 P 时，可以直接跳转：
start = 0, end = -1
for k in range(len(P)):
end = next_pos[end+1][P[k]]
if end == -1: 不存在
这样一次匹配 O(|P|)。
然后我们遍历所有起始位置 i，用上述跳转找结束位置，取最小长度窗口。
但这样还是 O(|S| |P|)。
步骤 5：进一步优化到 O(|S|)
我们可以用 DP 预处理出对于每个位置 i，匹配 P 的最小结束位置。
定义 end_at[i] = 若从 S 的 i 位置开始匹配 P，匹配完成后的结束位置。
我们可以倒着预处理：
- 先建一个数组 next_occurrence[ch] 按顺序存该字符在 S 中的所有位置。
- 然后对每个 i，我们找匹配 P 的序列：
其实可以倒着匹配 P：
设 match[j] = 匹配 P 的后缀 P[m-1:j] 时，在 S 中所需的最左起始位置。
更标准的方法（Leetcode 727 题解法）：
定义 dp[i][k] = 在 S[0:i] 中匹配 P[0:k] 时，最后一个字符在 S 中的位置。
转移：
如果 S[i] == P[k]，则 dp[i][k] = i（当 k>0 时，dp[i][k] 可以从 dp[i-1][k-1] 转移来，但我们要最小窗口，所以需要记录起始位置）。
实际上更简单的方法（非区间DP，是线性DP）：
我们定义 f[i][k] = 在 S[0:i] 中匹配 P[0:k] 的最短窗口的起始位置。
转移：
- 若 S[i] == P[k-1]：
如果 k==1: f[i][1] = i
否则 f[i][k] = f[i-1][k-1] - 若 S[i] != P[k-1]：f[i][k] = f[i-1][k]
然后长度 = i - f[i][|P|] + 1，取最小。
但这样是 O(|S| |P|) 时间，O(|S| |P|) 空间，可优化到 O(|P|) 空间。
步骤 6：最终简洁解法（动态规划）
我们用一个一维数组 dp[k] 表示当前匹配到 P 的第 k 个字符时，窗口的起始位置。
初始化 dp[0] = -1，dp[k>0] = ∞。
遍历 i = 0 到 |S|-1：
倒序更新 k 从 |P| 到 1（防止重复使用当前字符）：
如果 S[i] == P[k-1]：
dp[k] = dp[k-1] # 窗口起始位置继承自上一层
如果 k == |P|，则检查窗口长度 i - dp[k] + 1，更新最优解。
但更常见的写法（二维直观）：
dp[i][k] = 在 S[0..i] 中匹配 P[0..k] 的最小窗口的起始位置。
转移：
dp[i][k] = dp[i-1][k] # 不包含 S[i]
if S[i] == P[k-1]:
if k == 1:
dp[i][1] = i
else:
dp[i][k] = dp[i-1][k-1]
if k == |P| 且 dp[i][k] != -1:
长度 = i - dp[i][k] + 1，更新最优。
空间可滚动数组优化。
总结
这个问题的区间DP思路并不像石子合并那样典型，但它体现了在序列上定义状态，通过字符匹配进行转移的思想。
最终我们通过 O(|S| |P|) 的 DP 可以在字符串不长时有效求解，并且可以输出具体窗口。