状态表示 有点难想到 
f[i][j] 表示s,p 分别从i,j 到各自终点 是否匹配 不同于以往的做法 从前0~n遍历 这里需要用到

我的写法 太傻了 

    public int DP(int x, int y, char[] s, char[] p){
        if(x<=s.length&&y<=p.length&&f[x][y]!=-1) return f[x][y];
        if(x>s.length) return 0;
        if(y==p.length)
            return f[x][y] = s.length==x? 1:0;
        int ans = 0;
        if(y+1<p.length&&p[y+1]=='*'){
            ans = DP(x, y+2, s, p);
            //System.out.println(ans);
            if(ans==0&&(s[x]==p[y]||p[y]=='.')) ans = DP(x+1, y, s, p);
        }
        if(ans==0&&(p[y]=='.'||s[x]==p[y]))
            ans = DP(x+1, y+1, s, p);
        return f[x][y] = ans;
    }

y老的 真是 nb

public int dp(int x, int y, char[]s, char[] p){
        if(f[x][y]!=-1) return f[x][y];
        if(y==p.length)
            return f[x][y] = x==s.length?1:0;
        boolean ans;
        boolean match = x < s.length && (p[y]=='.'||s[x]==p[y]);
        if(y+1<p.length&&p[y+1]=='*')
            ans = dp(x, y+2, s, p)==1|| match&&dp(x+1, y, s, p)==1;
        else 
            ans = match&&dp(x+1, y+1, s, p)==1;
        return f[x][y] = ans ? 1 : 0;
    }

其实我觉得这题跟动态规划 以及 记忆话搜索 毛关系没有 
其实 f[i][j] 也可以保存 1~i 1~j 是否一样 写出来的 代码一样
下面是没有记忆话搜索的

public int dp(int x, int y, char[]s, char[]p){
       // if(f[x][y]!=-1) return f[x][y];
        if(y==p.length)
            return x==s.length? 1:0;
        boolean ans;
        boolean match = x < s.length && (p[y]=='.'||s[x]==p[y]);
        if(y+1<p.length && p[y+1]=='*')
            ans = dp(x, y+2, s, p)==1 || (match && dp(x+1, y, s, p)==1);
        else
            ans = match && dp(x+1, y+1, s, p)==1;
        return ans? 1:0;
    }