题目描述：
题解：仿照LCS构建一个dp[i][j]，表示s[i-1]与p[j-1]的匹配情况，dp[i][j] == 1 的时候表示完全匹配。状态转移如下:
当p[j-1]==‘*’的时候，要么‘*‘为空，要么‘*’匹配对应j-1位置的字符，也就是说这个时候的dp[i][j]由dp[i-1][j]以及dp[i][j-1]的状态决定；
当p[j-1]!=‘*‘的时候，dp[i][j]的状态由dp[i-1][j-1]以及s[i-1],p[j-1]值的i情况来确定。
AC代码如下：
bool isMatch(string s, string p) { int Lens = s.length(); int Lenp = p.length(); int dp[Lens+1][Lenp+1]; for(int i=0;i<=Lens;i++) for(int j=0;j<=Lenp;j++) dp[i][j] = 0; dp[0][0] = 1; for(int j=1;j<=Lenp;j++) dp[0][j] = dp[0][j-1] && p[j-1]==‘*‘; for(int i=1;i<=Lens;i++) { for(int j=1;j<=Lenp;j++) { if(p[j-1] == ‘*‘) { dp[i][j] = max(dp[i][j-1],dp[i-1][j]); } else { dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] | p[j-1] == ‘?‘ ); } } } if(dp[Lens][Lenp] == 1) return true; return false; }
原文：https://www.cnblogs.com/z1141000271/p/12157834.html