模板

     int len1=s.length(),len2=p.length();
        [][] dp=new [len1+1][len2+1]; //dp的类型就是返回的类型
        for(int i=1;i<=len2;i++) dp[0][]//注意dp[0][i]的初始化，注意是boolean且*可以匹配长度为0的字符串

        for(int i=1;i<=len1;i++){
            char c1=s.charAt(i-1);
            for(int j=1;j<=len2;j++){
               char c2=p.charAt(j-1);
              if(C1==c2) //如果相同
              else 如果是长度,则从dp[i][j-1]和dp[i-1][j-1]中取，如果是boolean，则观察*是否能匹配长度为0的字符序列
            }
        }
        return dp[len1][len2];

题目

10. 正则表达式匹配 else if(c2=='*')

44. 通配符匹配

72. 编辑距离

97. 交错字符串

115. 不同的子序列 这里的dp[i][j]的意思是前i个和前j个字符串匹配能匹配几个，如果匹配上了，那么就是选择要和不要，如果匹配不上，那么则只能选择不上

lcs

int len1=text1.length(),len2=text2.length();
        int[][] dp=new int[len1+1][len2+1];
        for(int i=1;i<=len1;i++){
            char c1=text1.charAt(i-1);
            for(int j=1;j<=len2;j++){
                char c2=text2.charAt(j-1);
                if(c1==c2) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }

题目

1092. 最短公共超序列 根据dp[][]的信息倒着推出 lca字串，最后根据lca子串补成一个最短子序列

1143. 最长公共子序列