//设dp[i][j]为s到第i个字符，p到第j个字符，模式是否匹配
class Solution {
public:
vector<vector<int>> dp;
bool dfs(string s, string p, int i, int j){
if(dp[i][j]!=-1)return dp[i][j];
if(j>=p.size()) return (i>=s.size());
bool res, curmatch = (i<s.size()&&(s[i]==p[j]||p[j]=='.')); //当前一对字符匹配上了
if(j+1<p.size()&&p[j+1]=='*') //p的下一个字符是*，要么选择匹配，要么就跳过这个模式
res = dfs(s,p,i,j+2)||(curmatch&&dfs(s,p,i+1,j));
else if(curmatch) //只要当前字符匹配上了，就可以往下推进
res = dfs(s,p,i+1,j+1);
else res = false; //当前字符没匹配上，状态自然是false
return dp[i][j]=res;
}
bool isMatch(string s, string p) {
int l1=s.size(), l2=p.size();
dp = vector<vector<int>>(l1+1,vector<int>(l2+1,-1));
return dfs(s,p,0,0);
}
};
bool dfs(int i, int j){
if(dp[i][j]!=-1)return dp[i][j]; //直接返回已有的值
if(j>=p.size()) return (i>=s.size()); //递归出口和其他剪枝
/*
递归语句(注意边界)
*/
return dp[i][j]=res; //返回值
}
