这道题用状态机最直观，奈何功力还是不够，而且觉得解这题用状态机很麻烦，最后只好看题解用DP，DP对我来说真的难。。。
DP就是打表，但是这个表中每个元素代表啥意思比较难想，必须要多积累经验才行。本题表元素dp[i,j]表示s串前i个字符是否能够和模式串p前j个字符匹配，假设s串长度sl，p串长度pl，dp表大小应该为(sl+1)×(pl+1)，于是dp[sl,pl]就是最终的解。状态转移方程如下：
这里主要是需要讨论p[j]的不同情况，如果p[j]不是星号，那就看p[j]与s[i]是否匹配，匹配的含义是指s[i]==p[j]或p[j]==’.’，若匹配那就看前边的是否匹配，若不匹配则dp[i,j]就是false。
若p[j]是星号，就得看s[i]和p[j-1]是否匹配，即s[i]是否和星号前那个字符匹配。若不匹配，那就得舍弃掉p[j-1]和p[j]这一对（任意字符加*表示匹配此字符0次或多次，这里不匹配，就表示匹配了0次，所以要舍弃掉这一对，去看舍弃这一对后的模式串是否能和s串匹配），看剩下的p是否能和s匹配，即dp[i,j]=dp[i,j-2]。若匹配，就要往前看，看把s[i]扔掉，剩下的s[0..(i-1)]是否还能匹配上p，或者看把p[j-1]和p[j]这一对舍弃后，剩下的p[0..(j-2)]是否能和s匹配上（即a*a*这种情况，本质上是尝试尽可能多地消除模式串，最大化匹配）
这里有个问题，就是边界dp[0,j]和dp[i,0]表示什么？显然i=0或j=0时表示s串或p串为空串，dp[0,0]就表示s和p都是空串，这时肯定是匹配的，即dp[0,0]=true，于是初始状态就有了。那么当j为0时表示模式串为空，如果s串不为空，那就肯定匹配不上，因此dp[i,0]=false，i≠0。而当i为0时，表示s串为空，这时就要讨论模式串p的情况了。
考虑p=”a*b*c*”这种情况，表示的是0或多个a加0或多个b加0或多个c，也就是说如果s串为空串时，仍然能够匹配上，因此不能简单地认为s串为空时p串永远匹配不上，也就是说不能简单认为dp[0,j]=false,j≠0。仔细观察p串，发现p[j]=’*’时，只要p[j-2]为true，则p[j]就为true，这是因为p[j-1]在p[j]（也就是’*’号）作用下，可以将其消除，只要看p[j-2]是不是true就好了，其背后的含义是p去掉数字加星后的前j-2号能不能匹配得上s的前i号。
string s = "abaab";
string p = "c*a*ba.*b";
Solution solution = new();
Console.WriteLine(solution.IsMatch(s, p));
public class Solution
{
public bool IsMatch(string s, string p)
{
int sl = s.Length;
int pl = p.Length;
s = '+' + s;
p = '+' + p;
bool[,] dp = new bool[sl + 1, pl + 1];
dp[0, 0] = true;
for (int j = 0; j < pl + 1; j++)
{
if (p[j] == '*' && j - 2 >= 0)
{
dp[0, j] = dp[0, j - 2];
}
}
for (int i = 1; i < sl + 1; i++)
{
for (int j = 1; j < pl + 1; j++)
{
switch (p[j])
{
case '*':
if (s[i] == p[j - 1] || p[j - 1] == '.')
{
dp[i, j] = dp[i - 1, j] || dp[i, j - 2];
}
else
{
dp[i, j] = dp[i, j - 2];
}
break;
case '.':
dp[i, j] = dp[i - 1, j - 1];
break;
default:
if (s[i] == p[j])
{
dp[i, j] = dp[i - 1, j - 1];
break;
}
break;
}
}
}
return dp[sl, pl];
}
}
这里为了简化实现，就额外在s和p前加了个特殊字符’+’，没有什么含义，只是为了让代码更简洁一些，C#默认初始化数组采用类型默认值，bool类型默认值就是false，因此这里只把赋值为true的情况写了出来，同样是为了简化代码。
以s=”abaab”，p=”caba.*b”为例，打表如下：
| dp | p | + | c | * | a | * | b | a | . | * | b |
| s | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| + | 0 | 1 | 1 | 1 | |||||||
| a | 1 | 1 | 1 | ||||||||
| b | 2 | 1 | |||||||||
| a | 3 | 1 | 1 | ||||||||
| a | 4 | 1 | 1 | ||||||||
| b | 5 | 1 | 1 |
