在正则表达式匹配的动态规划解法中，`dp[i][j] = dp[i][j - 2]` 是处理 `*` 字符时的关键状态转移方程，其核心逻辑如下： ### 1. **场景背景** 当模式串 `pattern` 的当前字符是 `*` 时（即 `pattern[j-1] == '*'`），我们需要考虑 `*` 的两种匹配方式： - **零次匹配**：`*` 匹配其前面的字符 **零次**（即忽略 `x*` 这两个字符）。 - **多次匹配**：`*` 匹配其前面的字符 **一次或多次**（即保留 `x*` 并继续匹配）。 ### 2. **`dp[i][j] = dp[i][j - 2]` 的含义** - **`j - 2` 的作用**： 跳过 `pattern` 中当前 `*` 及其前面的字符（即 `pattern[j-2]` 和 `pattern[j-1]`）。 例如：若 `pattern = "a*b"`，当 `j` 指向 `*` 时，`j-2` 会跳过 `"a*"`，只保留剩余模式（此处为空字符串）。 - **`dp[i][j-2]` 的意义**： 表示 **不消耗 `text` 的任何字符**，仅依赖 `pattern` 跳过 `x*` 后的子串是否匹配 `text` 的前 `i` 个字符。 ### 3. **为什么这样转移？** - **`*` 的零次匹配特性**： `*` 可以使其前面的字符出现 **零次**。例如： - `pattern = "a*b"` 匹配 `text = "b"`： 通过忽略 `"a*"`（即 `dp[1][2] = dp[1][0]`），此时 `text[0:1] = "b"` 匹配 `pattern` 跳过 `"a*"` 后的剩余部分（空字符串），需结合其他状态判断。 - **动态规划的状态依赖**： 当前状态 `dp[i][j]` 的值由子问题决定。跳过 `x*` 后，问题简化为： `text` 的前 `i` 个字符 是否匹配 `pattern` 跳过 `x*` 后的子串（即 `pattern[0:j-2]`）。 ### 4. **示例验证** 假设： - `text = "aa"`, `pattern = "a*"` 初始化：`dp[0][0] = true`（空串匹配空串）。 处理 `j=2`（`pattern[1] = '*'`）： - `dp[0][2] = dp[0][0] = true`（`text` 为空时，`a*` 匹配零次）。 - `dp[1][2]`：`text[0]='a'` 匹配 `a*`（零次或多次），需结合 `dp[0][2]`（零次）和 `dp[1][2]`（多次）→ 最终为 `true`。 - `dp[2][2]`：同理，最终为 `true`。 ### 5. **与其他转移方程的对比** - **多次匹配**：`dp[i][j] = dp[i-1][j]` 表示 `*` 匹配其前面的字符 **至少一次**，需消耗 `text` 的一个字符（`i-1`），而 `pattern` 不变（因为 `*` 可继续匹配）。 - **零次匹配**：`dp[i][j] = dp[i][j-2]` 表示 `*` 匹配零次，`pattern` 跳过 `x*`，`text` 不消耗字符。 ### 总结 `dp[i][j] = dp[i][j-2]` 是动态规划中处理 `*` 的 **零次匹配** 的核心逻辑： **跳过模式串中的 `x*`，直接依赖更短的模式串（`pattern[0:j-2]`）与当前 `text` 的匹配结果**。 这一转移方程与 `dp[i][j] = dp[i-1][j]`（多次匹配）共同构成了 `*` 的完整匹配逻辑。

根据参考资料中对正则表达式 `*` 操作符的定义： **`*` 匹配零个或多个前面的那一个字符**。 对于模式 `a*`： - `a` 是 `*` 前面的字符。 - `*` 允许 `a` 出现 **零次**（即完全跳过 `a`），此时匹配结果为空字符串 `""`。 ### 示例验证： - 输入 `s = ""`（空字符串），`p = "a*"`： - `a*` 可以匹配零个 `a` → 结果为 `""`，与 `s` 完全匹配 → **输出 `true`**。 - 输入 `s = "aa"`，`p = "a*"`： - `a*` 可以匹配两个 `a`（`a` 出现两次）→ 结果为 `"aa"`，与 `s` 匹配 → **输出 `true`**。 ### 总结： `a*` 的灵活性在于： 1. **零次匹配**：跳过 `a`，匹配空字符串 `""`。 2. **多次匹配**：匹配一个或多个 `a`（如 `"a"`, `"aa"`, `"aaa"` 等）。 因此，`a*` 能匹配 `""` 是其核心特性之一。