算法：动态规划

1.状态表示

f[i][j]表示s中从1-i(包含i)，p中从1-j(包含j)，p,s是否匹配，0/1；

2.状态转移

 1.1：根据p[j],s[i]的不同情况将f[i][j]分成由不同状态转移过来的，注意只要有一种能匹配的状态能够转移，f[i][j]=1;
      即f[i][j]的真假值由划分的各个集合求并；
 1.2:
    2.1: if(p[j]!='*'):
         最后一位如果匹配的话，f[i][j]就由前面的匹配情况确定：
         if(s[i]==p[j]) f[i][j]|=f[i-1][j-1];
         if(p[j]=='.')  f[i][j]|=f[i-1][j-1];

         总结： if(i>0&&p[j]!='*') f[i][j]=f[i-1][j-1]&&(s[i]==p[j]||p[j]=='.');

    2.2: if(p[j]=='*')
         最后一位为"*"时，* 对前面一位发挥不同的作用，需要依次考虑，~代表前一位字母,
         将~*视为整体去匹配，对于单独的~字符，不用考虑
         ~*=0：f[i][j-2];
         ~*=1: f[i-1][j-2]&&(s[i]匹配p[j-1]);
         ~*=2: f[i-2][j-2]&&(s[i]匹配p[j]&&s[i-1]匹配p[j-1]),p[j]=p[j-1];即：
               f[i-1][j-2]&&(s[i]匹配p[j-1]&&s[i-1]匹配p[j-1]);
         设~*max=k;


    f[i][j]=f[i][j-2]||(f[i-1][j-2]&&s[i])(f[i-2][j-2]&&s[i]i&&s[i-1]).... (f[i-k][j-2]&&s[i]&&...s[i-k+1])

         观察到：
  f[i-1][j]=f[i-1][j-2]||(f[i-2][j-2]&&s[i-2))......(f[i-k][j-2]&&s[i-1]&&...&&s[i-k+1])

         总结：f[i][j]=f[i][j-2]||(f[i-1][j]&&(s[i]==p[j-1]||p[j-1]=='.'));

3.边界问题

注意转移方程的i-1，j-2等数组的越界判定
s为空串时，p=a*可以匹配，即f[0][1]在一些情况下可能为true，需要判定；
p为空串时，s非空的话根本不能匹配，即f[1...n][0]==false;
综上所述：
f[0][0]=true;s从0开始判断，p从1开始判断

4.代码

class Solution {
public:
    bool isMatch(string s, string p) {
     int n=s.size(),m=p.size();
     s=' '+s;
     p=' '+p;
     vector<vector<bool>> f(n+1,vector<bool>(m+1,false));
     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(i&&p[j]!='*')
             f[i][j]=f[i-1][j-1]&&(s[i]==p[j]||p[j]=='.');
              else if(p[j]=='*')
             f[i][j]=f[i][j-2]||(i&&f[i-1][j]&&(s[i]==p[j-1]||p[j-1]=='.'));
         }
     }
     return f[n][m];
    }
};

我写的怎么样啊，莱纳.jpg