https://leetcode.cn/problems/regular-expression-matching/submissions/581130298/

当前s串的位置i和p串的位置j，以j+1是不是*号展开讨论

int n,m;
string ss,pp;
int dp[30][30];
int dfs(int x,int y)
{
    if(dp[x][y]) return dp[x][y];
    int ans=2;
    if(x==n+1)
    {
        if(y==m+1) ans=1;
        else
        {
            if(y+1<=m&&pp[y+1]=='*'&&dfs(x,y+2)==1) ans=1;
        }
    }
    else
    {
        if(y==m||pp[y+1]!='*') 
        {
            if((ss[x]==pp[y]||pp[y]=='.')&&dfs(x+1,y+1)==1) ans=1;
        }
        else
        {
            int p0=dfs(x,y+2);
            //if(ss[x]!=pp[y]&&pp[y]!='.'&&dfs(x,y+2)==1) ans=1;
            //else if((ss[x]==pp[y]||pp[y]=='.')&&dfs(x+1,y)==1) ans=1;
            int p1=(ss[x]==pp[y]||pp[y]=='.')&&(dfs(x+1,y)==1);
            if(p1==1||p0==1) ans=1;
        }
    }
    dp[x][y]=ans;
    return ans;
}
class Solution {
public:
    bool isMatch(string s, string p) {
        memset(dp,0,sizeof(dp));
        n=s.length();
        m=p.length();
        ss=" "+s;
        pp=" "+p;
        dp[n+1][m+1]=1;
        for(int i=n+1,j=m+1;j>=1;j--) if(j+1<=m&&pp[j+1]=='*'&&dp[i][j+2]) dp[i][j]=1;
        for(int i=n;i>=1;i--)
        {
            for(int j=m;j>=1;j--)
            {
                if(j==m||pp[j+1]!='*')
                {
                    if((ss[i]==pp[j]||pp[j]=='.')&&dp[i+1][j+1]) dp[i][j]=1;
                }
                else
                {
                    int p0=dp[i][j+2];
                    int p1=(ss[i]==pp[j]||pp[j]=='.')&&dp[i+1][j];
                    if(p0||p1) dp[i][j]=1;
                }
            }
        }
        //if(dfs(1,1)==1) return true;
        //else return false;
        return dp[1][1];
    }
};