区间动态规划例题：正则表达式匹配问题 题目描述 给定一个字符串 s 和一个字符模式 p ，实现支持 '.' 和 '*' 的正则表达式匹配。 '.' 匹配任意单个字符。 '*' 匹配零个或多个前面的元素。 匹配需覆盖整个字符串 s ，而非部分匹配。 示例 输入： s = "aa", p = "a" ，输出： false （ p 无法匹配整个 s ）。 输入： s = "aa", p = "a*" ，输出： true （ a* 可匹配两个 a ）。 输入： s = "ab", p = ".*" ，输出： true （ .* 可匹配任意字符串）。 解题思路 使用区间动态规划（实际是二维动态规划），定义 dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配。需分情况讨论模式 p 的当前字符是否为 * 。 步骤详解 状态定义 dp[i][j] ： s[0:i] 与 p[0:j] 是否匹配（ i 和 j 表示长度）。 初始状态 dp[0][0] = true （空字符串匹配空模式）。 初始化边界情况 当 s 为空时，若 p 的偶数位为 * （如 a*b*c* ），可能匹配空字符串。 遍历 p ，若 p[j-1] == '*' 且 dp[0][j-2] 为真，则 dp[0][j] = true 。 状态转移方程 遍历 i （从1到 s 长度）和 j （从1到 p 长度）： 情况1： p[j-1] 不是 '*' 当前字符需直接匹配： s[i-1] == p[j-1] 或 p[j-1] == '.' 。 若匹配成功，则 dp[i][j] = dp[i-1][j-1] （依赖前一个状态）。 情况2： p[j-1] == '*' 需考虑 p[j-2] （即 * 前的字符）和匹配次数： 匹配0次 ：忽略 p 的 x* 部分， dp[i][j] = dp[i][j-2] 。 匹配1次或多次 ：需满足 s[i-1] 与 p[j-2] 匹配（相等或 p[j-2] == '.' ），且 s 的前缀需匹配当前模式，即 dp[i][j] = dp[i-1][j] 。 综合两种情况： 最终结果 返回 dp[len(s)][len(p)] 。 示例推导（s="aa", p="a* "） 初始化： dp[0][0]=true ， dp[0][1]=false （ p[0]='a' ）， dp[0][2]=true （ p[1]='*' ，匹配0次时忽略 a* ）。 计算 i=1 （ s[0]='a' ）： j=1 ： p[0]='a' 匹配 s[0] ， dp[1][1] = dp[0][0] = true 。 j=2 ： p[1]='*' ，匹配0次时 dp[1][2]=dp[1][0]=false ；匹配多次时需 s[0] 匹配 p[0] （成立）且 dp[0][2]=true ，故 dp[1][2]=true 。 计算 i=2 （ s[1]='a' ）： j=2 ：匹配0次不成立（ dp[2][0]=false ）；匹配多次时需 s[1] 匹配 p[0] （成立）且 dp[1][2]=true ，故 dp[2][2]=true 。 结果： dp[2][2]=true 。 关键点 '*' 的处理需结合前一个字符，并考虑匹配0次或多次。 边界初始化需注意空字符串与模式的匹配。 时间复杂度：O(mn)，空间复杂度可优化至 O(n)。