链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/
状态表示：f[i][j] 表示s[i,..]与p[j,...]匹配
状态转换：
1.p[j]是正常字符，f[i][j] = s[i] == p[j] && f[i + 1][j + 1]
2.p[j]是‘.‘，f[i][j] = f[i + 1][j + 1]
3.p[j + 1]是‘*‘，f[i][j] = f[i][j + 2] || f[i + 1][j]
class Solution { public: vector<vector<int>>f; int n, m; bool isMatch(string s, string p) { n = s.size(); m = p.size(); f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1)); f[n][m] = 1; dp(0, 0, s, p); return dp(0, 0, s, p); } int dp(int x, int y, string &s, string &p) { if (f[x][y] != -1) return f[x][y]; if (y == m) return f[x][y] = x == n; bool first_match = x < n && (s[x] == p[y] || p[y] == ‘.‘); bool ans; if (y + 1 < m && p[y + 1] == ‘*‘) { ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p); } else ans = first_match && dp(x + 1, y + 1, s, p); return f[x][y] = ans; } };
原文：https://www.cnblogs.com/clown9804/p/12346575.html