区间动态规划例题：带通配符的模式匹配问题（'?'和'* '匹配） 题目描述 给定一个输入字符串 s 和一个模式字符串 p ，模式中可能包含两种通配符： '?' 可以匹配任意 单个 字符。 '*' 可以匹配任意 多个 字符（包括零个字符）。 要求判断模式 p 是否能够完全匹配整个字符串 s （即 s 的所有字符都被 p 匹配，且 p 的所有非通配符字符都按顺序匹配 s ）。 示例 输入： s = "adceb" , p = "*a*b" 输出： true （解释： '*' 匹配空字符串， 'a' 匹配 'a' ， '*' 匹配 "dce" ， 'b' 匹配 'b' ） 输入： s = "acdcb" , p = "a*c?b" 输出： false （最后一个 '?' 无法匹配 'c' ，因为 'b' 已经占用最后一个字符） 解题思路 使用区间动态规划，定义 dp[i][j] 表示字符串 s 的前 i 个字符（即 s[0:i-1] ）是否与模式 p 的前 j 个字符（即 p[0:j-1] ）匹配。 状态转移方程推导 基础情况 ： dp[0][0] = true ：两个空字符串匹配。 对于 dp[0][j] （即 s 为空）：只有当 p 的前 j 个字符全部为 '*' 时才为 true ，因为 '*' 可以匹配零个字符。 对于 dp[i][0] （即 p 为空）：只有 s 也为空时才为 true ，否则为 false 。 一般情况（i > 0, j > 0） ： 若 p[j-1] 是普通字符：需满足 s[i-1] == p[j-1] 且 dp[i-1][j-1] 为 true 。 若 p[j-1] 是 '?' ：它一定匹配 s[i-1] ，只需检查 dp[i-1][j-1] 。 若 p[j-1] 是 '*' ： 匹配零个字符：忽略 '*' ，检查 dp[i][j-1] 。 匹配多个字符： '*' 匹配 s[i-1] 并继续匹配前面的字符，检查 dp[i-1][j] 。 综上： dp[i][j] = dp[i][j-1] || dp[i-1][j] 。 动态规划表填充过程 以 s = "adceb" , p = "*a*b" 为例： 初始化 dp[0][0] = true ，且 dp[0][1] = true （因为 p[0] = '*' ）。 按行填充（ i 从 1 到 5， j 从 1 到 4）： i=1, j=1 ： p[0]='*' ，匹配零个字符时 dp[1][0]=false ，匹配多个字符时 dp[0][1]=true → dp[1][1]=true 。 后续步骤严格按转移方程计算，最终 dp[5][4] = true 。 优化提示 可压缩 DP 数组至一维以节省空间。 若模式中连续出现 '*' ，可合并为一个 '*' 以提升效率。 复杂度分析 时间复杂度：O(mn)，其中 m = len(s) ， n = len(p) 。 空间复杂度：O(mn)（可优化至 O(n)）。