问题
传送门：https://leetcode.cn/problems/regular-expression-matching/description/
思路
两个字符串进行匹配，一个是主串，一个是模式串，如何匹配？和比较经典的最长递增子序列问题相似地，我们也可以采取动态规划的思想来解出此题。
对于给定的主串$s$，以及模式串$p$，它们的长度分别为$m,n$，我们定义一个数组$dp[m+1][n+1]$，其中$dp[i][j]$表示主串的前$i$个字符组成的子串和模式串的前$j$个字符组成的子串匹配，即$s[0:i]$和$p[0:j]$匹配。
借助python包numpy写法，对于字符串str，$str[i:j]$表示截取字符串str的$[i,j)$区间子串。
由此我们可以仿照“最大编辑距离”问题中的思考方式，考虑当前两个字符串的末尾字符，从而得出状态转移方程。
若$p[j-1]=*$
这种情况稍显复杂。此时必须选取$p[i-2]$，看它是否和主串末尾字符匹配：
若$p[j-2]=s[i-1]$
也就是说，主串末尾字符$s[i-1]$和模式串的$p[i-2:i]$（$x$整体，$x$为普通字符）匹配上了。*关键来了。这时，可以有三种方式继续将$s[0:i-1]$与模式串$p$进行匹配。
保留$x*$整体，匹配$s[0:i-1]$与$p[0:j]$，即$dp[i-1][j]$
举个例子，如$\mathrm{abaaa}$与$\mathrm{aba*}$
舍弃$x*$整体，且舍弃刚刚的匹配策略，继续匹配$s[0:i]$与$p[0:j-2]$，即$dp[i][j-2]$
举个例子，如$\mathrm{abaaa}$与$\mathrm{abaaaa*}$
舍弃$x*$整体，但是采取刚刚的匹配策略，继续匹配$s[0:i-1]$与$p[0:j-2]$，即$dp[i-1][j-2]$
举个例子，如$\mathrm{abaaa}$与$\mathrm{abaaa*}$
若$p[j-2]\ne s[i-1]$
这种情况较简单，此时要想匹配上，只能按$x$中的$x$一次也不出现来算，且*此时主串末尾字符$s[i-1]$是没有匹配上的。因此接下来匹配$s[0:i]$与$p[0:j-2]$，即$dp[i][j-2]$
若$p[j-1]\ne *$
这种情况最为简单，判断主串末位字符和模式串末位字符是否匹配（注意考虑通配符$.$），如果它们匹配，进一步判断主串的前$i-1$个字符子串和模式串的前$j-1$个字符子串是否匹配，描述为两个条件的交：$\mathrm{singleMatch(p[j-1],s[i-1])} \&\& dp[i-1][j-1]$
状态转移
综合得到状态转移方程：
$dp[i][j]=\begin{cases} \mathrm{singleMatch(p[j-1], s[i-1]) \&\& dp[i-1][j-1]}, \quad p[j-1] \ne \\\\ \mathrm{dp[i-1][j] || dp[i][j-2] || dp[i-1][j-2], \quad p[j-1]= \&\& p[j-2]=s[i-1] } \\\\ \mathrm{dp[i][j-2],\quad otherwise} \end{cases}$
边界情况
状态转移、边界条件是动态规划的关键。下面思考一下边界条件如何书写。以实际的例子进行说明：
$m=n=0$时
此时字符串匹配成功，比较理想的情况，$dp[0][0]=1$
$m=0,n>0$时
例如
""与"a*b*"、""与"b*c"，事实上当$p[i-1]=*$时，有$dp[0][i]=dp[0][i-2]$（比如第一个例子$dp[0][0]=dp[0][2]=dp[0][4]=1$，细品）；其余情况匹配失败$m>0,n=0$时
例如
"abac"与""，此时必然匹配失败，$dp[i][0]=0$
代码
采用自底向上的迭代写法，编写完整的动态规划代码如下。
class Solution {
public:
int dp[25][25];
bool isSingleMatch(char ch1, char ch2) {
if(ch1 == '.' || ch2 == '.') return true;
return ch1 == ch2;
}
bool isMatch(string s, string p) {
// dp[i][j]表示s[0:i-1]是否匹配p[0:i-1]
// 考虑边界
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
int i, j;
// s="" p="a*b*ccd*"
for(i=1; i<=p.size(); i++) {
if(p[i-1] == '*') dp[0][i] = dp[0][i-2];
}
// 迭代
for(i=1; i<=s.size(); i++) {
for(j=1; j<=p.size(); j++) {
if(p[j-1] == '*') {
if(isSingleMatch(p[j-2], s[i-1])) dp[i][j] = dp[i-1][j] || dp[i-1][j-2] || dp[i][j-2];
else dp[i][j] = dp[i][j-2];
} else {
dp[i][j] = isSingleMatch(p[j-1], s[i-1]) && dp[i-1][j-1];
}
}
}
return dp[s.size()][p.size()];
}
};当然，也可以编写自底向上的带备忘录式动态规划代码。
class Solution {
public:
bool isSingleMatch(char ch1, char ch2) {
if(ch1 == '.' || ch2 == '.') return true;
return ch1 == ch2;
}
int dp[25][25];
string S, P;
int DP(int i, int j) {
// s[0:i), p[0:j)是否匹配，前i、j个字符
if(dp[i][j] != -1) return dp[i][j];
if(P[j-1] == '*') {
if(!isSingleMatch(S[i-1], P[j-2])) {
// aaa ab*
return dp[i][j] = DP(i, j-2);
} else {
// aaa aa*
return dp[i][j] = DP(i, j-2) || DP(i-1, j-2) || DP(i-1, j);
}
} else {
if(isSingleMatch(S[i-1], P[j-1])) {
return dp[i][j] = DP(i-1, j-1);
} else return dp[i][j] = 0;
}
}
bool isMatch(string s, string p) {
// s = "aa"
// p = "a*"
int i, j;
S = s, P = p;
memset(dp, -1, sizeof(dp));
dp[0][0] = 1;
for(i=1; i<=s.size(); i++) dp[i][0] = 0;
for(i=1; i<=p.size(); i++) {
if(p[i-1] == '*') dp[0][i] = dp[0][i-2];
else dp[0][i] = 0;
}
for(i=1; i<=s.size(); i++) {
for(j=1; j<=p.size(); j++) {
dp[i][j] = DP(i, j);
}
}
return dp[s.size()][p.size()];
}
};
