区间动态规划例题：正则表达式匹配问题（'.'和'* '匹配，进阶版） 题目描述： 给定一个字符串 s 和一个模式串 p ，模式串中可能包含以下特殊字符： . 匹配任意单个字符 * 匹配零个或多个前面的元素 要求实现一个函数，判断字符串 s 是否完全匹配模式 p 。匹配需覆盖整个字符串 s ，而不仅是部分子串。 解题思路（区间动态规划） 步骤1：定义状态 我们使用二维动态规划数组 dp[i][j] ，其中： dp[i][j] 表示 s 的前 i 个字符（即 s[0...i-1] ）是否能被 p 的前 j 个字符（即 p[0...j-1] ）匹配。 步骤2：初始化边界条件 dp[0][0] = true ：空字符串匹配空模式。 对于 dp[0][j] （即 s 为空但 p 非空）： 只有当 p 的字符形式为 a*b*c*... 时（即偶数位置的字符为 * 且可以匹配零次），才可能为 true 。 具体规则：若 p[j-1] == '*' 且 dp[0][j-2] 为真，则 dp[0][j] = true 。 步骤3：状态转移方程 遍历 i 从 0 到 len(s) ， j 从 1 到 len(p) ： 如果 p[j-1] 不是 '*' ： 要求 s 的第 i 个字符（ s[i-1] ）必须与 p 的第 j 个字符（ p[j-1] ）匹配（相等或 p[j-1] == '.' ），并且前一部分也需匹配： \[ dp[ i][ j] = dp[ i-1][ j-1] \quad \text{且} \quad (s[ i-1] == p[ j-1] \ \text{或} \ p[ j-1 ] == '.') \] 如果 p[j-1] == '*' ： 此时 p[j-2] 是 * 前面的字符（记作 x ）， x* 可以匹配零次或多次： 匹配零次 ：直接忽略 x* ，即 dp[i][j] = dp[i][j-2] 。 匹配一次或多次 ：要求 s[i-1] 与 x 匹配（ x == '.' 或 x == s[i-1] ），并且 s 的前 i-1 个字符需与 p 的前 j 个字符匹配（即继续用 x* 匹配前面的字符）： \[ dp[ i][ j] = dp[ i-1][ j] \quad \text{且} \quad (s[ i-1] == p[ j-2] \ \text{或} \ p[ j-2 ] == '.') \] 综上，此时 dp[i][j] = dp[i][j-2] || (dp[i-1][j] \&\& 字符匹配) 。 步骤4：最终结果 返回 dp[len(s)][len(p)] ，表示整个 s 是否匹配整个 p 。 示例演示 设 s = "aab" ， p = "c*a*b" ： 初始化： dp[0][0] = true ， dp[0][1] = false （ p[0]='c' ）， dp[0][2] = true （ c* 匹配零次）， dp[0][3] = false ， dp[0][4] = true （ c*a* 匹配零次）。 计算过程略（按上述规则递推），最终 dp[3][5] = true ，匹配成功。 关键点 注意 * 的处理：优先考虑匹配零次的情况，再判断能否匹配多次。 初始化时需处理 p 开头为 a*b*... 的形式。 时间复杂度 O(nm)，空间复杂度可优化至 O(m)。