[数据结构与算法]经典动态规划：字符串编辑——（LC10困难）

题目：

输入是一个待匹配字符串和一个用字符串表示的正则表达式，输出是一个布尔值，表示是否
可以匹配成功。

题解：

状态：
首先状态 dp 一定能自己想出来。
dp[i][j] 表示 s 的前 i个是否能被 p 的前 j个匹配

转移方程：

已知 dp[i-1][j-1] 意思就是前面子串都匹配上了，不知道新的一位的情况。
那就分情况考虑，所以对于新的一位 p[j] s[i] 的值不同，要分情况讨论：

考虑最简单的 p[j] == s[i] : dp[i][j] = dp[i-1][j-1]
然后从 p[j] 可能的情况来考虑，让 p[j]=各种能等于的东西。

第一个难想出来的点：怎么区分 *? 的两种讨论情况
首先给了 *，明白 * 的含义是 匹配零个或多个前面的那一个元素，所以要考虑他前面的元素 p[j-1]。* 跟着他前一个字符走，前一个能匹配上 s[i]，* 才能有用，前一个都不能匹配上 s[i]，* 也无能为力，只能让前一个字符消失，也就是匹配 00 次前一个字符。
所以按照 p[j-1] 和 s[i] 是否相等，我们分为两种情况：

3.1 p[j-1] != s[i] : dp[i][j] = dp[i][j-2]
这就是刚才说的那种前一个字符匹配不上的情况。
比如(ab, abc * )。遇到 * 往前看两个，发现前面 s[i] 的 ab 对 p[j-2] 的 ab 能匹配，虽然后面是 c*，但是可以看做匹配 00 次 c，相当于直接去掉 c *，所以也是 True。注意 (ab, abc**) 是 False。
3.2 p[j-1] == s[i] or p[j-1] == "."：
* 前面那个字符，能匹配 s[i]，或者 * 前面那个字符是万能的 .
因为 . * 就相当于 . .，那就只要看前面可不可以匹配就行。
比如 (##b , ###b *)，或者 ( ##b , ### . * ) 只看 ### 后面一定是能够匹配上的。
所以要看 b 和 b * 前面那部分 ## 的地方匹不匹配。

第二个难想出来的点：怎么判断前面是否匹配

dp[i][j] = dp[i-1][j] // 多个字符匹配的情况?? ?
or dp[i][j] = dp[i][j-1] // 单个字符匹配的情况
or dp[i][j] = dp[i][j-2] // 没有匹配的情况? ?

具体多种详细题解可以去力扣10题查找（还是比较经典的一道题目）

class Solution {
    public boolean isMatch(String s, String p) {
       int m=s.length();
       int n=p.length();

       boolean[][]f=new boolean[m+1][n+1];
       f[0][0]=true;
       for(int i=0;i<=m;++i){
           for(int j=1;j<=n;++j){
           if(p.charAt(j-1)=='*'){
               f[i][j]=f[i][j-2];//2个字符
               if(matches(s,p,i,j-1)){
                   f[i][j]=f[i][j]||f[i-1][j];
               }
           }else{
               if(matches(s,p,i,j)){
                   f[i][j]=f[i-1][j-1];
               }
           }
           }
       }
       return f[m][n];
    }
    public boolean matches(String s,String p,int i,int j){
        if(i==0){
            return false;
        }
        if(p.charAt(j-1)=='.'){
            return true;
        }
        return s.charAt(i-1)==p.charAt(j-1);//这是上面的不满足执行的
    }
}