DP状态表示

这道题是一个二维状态表示的DP，用f[i][j]表示s前i个字符和p前j个字符可以相匹配。

状态转换方程

1. 当p[j+1]=='*'时我们跳过这一次判断，因为*只有和前面一个字符连起来的时候才有意义。
2. 当p[j]=='*'时
3. X*表示0个字符，那么f[i][j]由f[i][j-2]转换过来
4. X*表示1个X字符，那么f[i][j]由i&&f[i-1][j]&&s[i]==p[j-1]转换过来
5. 不需要考虑X*表示2个及以上X字符的情况，因为如果i+1轮情况当中s字符串需要p[j]发力多给一个X字符的话就会从i&&f[i-1][j]&&s[i]==p[j-1]转换过来的
6. 当p[j]!='*'时，f[i][j]由i&&f[i-1][j-1]&&(s[i]==p[j]||p[j]==’.’)转换过来

class Solution {
public:
    bool isMatch(string s, string p) {
        int n=s.size(),m=p.size();
        // vector<vector<bool>> f(n+1,vector<bool>(m+1));
        bool f[n+1][m+1];
        memset(f,0,sizeof(f));
        //如果要用数组则必须使用memset初始化，否则就用vector来自动初始化，要么放在全局开数组
        s=' '+s;
        p=' '+p;
        f[0][0]=true;
        for(int i=0;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(j+1<=m&&p[j+1]=='*')continue;
                if(p[j]=='*')
                {
                    f[i][j]=f[i][j-2]||i&&f[i-1][j]&&(s[i]==p[j-1]||p[j-1]=='.');
                }
                else
                {
                    f[i][j]=i&&f[i-1][j-1]&&(s[i]==p[j]||p[j]=='.');
                }
            }
        }
        return f[n][m];
    }
};