正则表达式匹配

关键不是背模板，而是看懂为什么这题适合二维 DP。

① 基底 dp[0][0]=true：空串匹配空模式：空串和空模式一定匹配 → dp[0][0]=true，整张表从这里出发。

② x* 可匹配空串(第 0 行)：c* 可以匹配「0 个 c」→ 跳过 c*，dp[0][2] 继承 dp[0][0]=1；同理 a* 让 dp[0][4] 继承 dp[0][2]=1。

③ 普通字符(或 .)相等 → 继承左上：s 的 'a' 与 p 的 'a' 相等(若 p 是 '.' 也算匹配)→ 这格继承左上 dp[0][2]=1。

④ 遇到 *，先试「匹配 0 次」→ 看左 2 列：遇到 c*，先考虑「一个 c 都不要」→ 跳过 c* 这两位，看 dp[1][0]=0 → 这格为 0。

⑤ * 匹配多次：前字符能吃当前 → 看上一行：a* 且 'a' 能吃掉 s 的 'a' → 复用「吃掉这个 a 之前」的结果 dp[0][4]=1 → 这格为 1。

⑥ a* 继续再吃一个 a：a* 再吃 s 的第二个 a → dp[2][4] 看上一行 dp[1][4]=1 → 仍为 1。

⑦ 结尾 b 相等 → 继承左上：s 的 'b' 与 p 的 'b' 相等 → dp[3][5] 继承左上 dp[2][4]=1。

⑧ 答案在右下角 dp[m][n]：右下角 dp[3][5]=1 → "aab" 匹配 "c*a*b"，返回 true。

把这句话记住，下次遇到同类题，就能更快选出方向。

迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

边界三连：边界三连：极端输入先过一遍。

几个高频追问，记住答法。