最近遇到好几个这种类型的问题，主要就是给你两个字符串，然后进行字符串自己的匹配或者转化，这类问题就是采用动态规划，二维的和一维的，现在对这一类问题做一个总结

题目一[leetcode72]https://leetcode.com/problems/edit-distance/

给了两个字符串word1和word2，使用删除，添加，替换操作从word1转化到word2，每个操作代价为1，需要找到最小代价的转化方法。

算法原理&算法步骤

方法一：二维dp

使用一个二维的数组dp[][]，其中dp[i+1][j+1]表示word1[0,i]转化到word2[0,j]需要的最小代价，那么现在来求解动态规划方程

考虑现在word1[i]和Word2[j],
如果word1[i]=word2[j],那么dp[i+1][j+1]=dp[i][j]
否则word1[i]！=word2[j]时，有这么几种情况
1. abcd abce 替换 dp[i+1][j+1]=dp[i][j]
2.abc abcd 添加 dp[i+1][j+1]=dp[i+1][j]
3.adcd abd 删除 dp[i+1][j+1]=dp[i][j+1]

有了上述动态规划的方程，接下来的问题就简单多了
需要特别注意的是dp[][]数组的第一行和第一列的初始化
第一行表示word1取了""，那么dp[0][j+1]=j+1(添加操作)
第一列表示word2去了""，那么dp[i+1][0]=i+1(删除操作)

代码：

public class Solution {
    public int minDistance(String word1, String word2) {
        int len1=word1.length();
        int len2=word2.length();
        int[][] dp=new int[len1+1][len2+1];//dp[i+1][j+1]表示word1[0,i],word2[0,j]的cnovert需要进行的编辑次数
        
        for(int j=0;j<len2;j++){
            dp[0][j+1]=j+1;
        }
        for(int i=0;i<len1;i++){
            dp[i+1][0]=i+1;
        }
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                if(word1.charAt(i)==word2.charAt(j)){
                    dp[i+1][j+1]=dp[i][j];
                }
                else{
                    dp[i+1][j+1]=Math.min(dp[i][j],Math.min(dp[i][j+1],dp[i+1][j]))+1;
                                         //abcc abcd        abcd abc    abc abcd
                }
            }
        }
        return dp[len1][len2];
    }
}

方法二：一维dp

现在回过头来看看二维动态规划方程,

dp[i+1][j+1]=dp[i][j]，word1[i]=word2[j]
dp[i+1][j+1]=min(dp[i][j],dp[i+1][j],dp[i][j+1])

dp[i+1][j+1]只与dp[i][j]、dp[i+1][j]、dp[i][j+1]有关，由于计算顺序也是一行一行的来，所以可以考虑进行复用，只使用一个一维的数组dp,但是假设在计算j-1的时候就更新了dp[j ]，那么 上一行的dp[j]就不见了，在计算dp[j+1]的时候是需要上一行的dp[j]的，所以这里之前先不更新，在计算了dp[j+1]之后再去更新dp[j]，并且用一个变量prev记忆dp[j],这样

dp[j+1]=dp[j]，word1[i]=word2[j]
dp[j+1]=min(dp[j],dp[j+1],prev)  word1[i]!=word2[j]，
其中dp[j+1]代表当前行j位置，dp[j]代表上一行j-1位置，prev代表当前行j-1位置

也是需要注意的是，word1取""的时候，也就是dp最开始的初始化
还有word2取""，也就是求解每一行的时候开始的时候的prev的初始化。
另外一点，由于dp[j+1]是在下一列才更新，所以最后一列在循环中没有得到更新，在一行计算完成后，需要给dp[word2.length]=prev单独赋值

public class Solution {
    public int minDistance(String word1, String word2) {
        int len1=word1.length();
        int len2=word2.length();
        int[] dp=new int[len2+1];
        for(int j=0;j<len2;j++){
            dp[j+1]=j+1;
        }
        int prev;
        int cur;
        for(int i=0;i<len1;i++){
            prev=i+1;
            for(int j=0;j<len2;j++){
                if(word1.charAt(i)==word2.charAt(j))
                    cur=dp[j];
                else{
                    cur=Math.min(dp[j+1],Math.min(dp[j],prev))+1;
                }
                dp[j]=prev;
                prev=cur;
            }
            dp[len2]=prev;
        }
        return dp[len2];
    }
}

题目二

[leetcode10]https://leetcode.com/problems/regular-expression-matching/
表达式匹配，给了字符串s和p,需要对s和p进行匹配,其中p的"."表示任意一个字符,p中的"*"，表示0个或多个前边的字符

算法原理&算法步骤

同样是使用一个二维动态规划数组dp[][]，其中dp[i+1][j+1]表示s[0,i],p[0,j]时候能够匹配,那么现在来求解动态规划方程

假如s[i]==p[j]||p[j]=='.'  那么 dp[i+1][j+1]=dp[i][j]
否则，如果p[j]=='*'，如果s[i]!=p[j-1]&&p[j-1]!='.',直接抛弃a*，dp[i+1][j+1]=dp[i+1][j-1]
      否则，表明当前位置p s不同，前一个位置可以匹配，那么有以下几种可能
            abc abc* 直接抛弃* dp[i+1][j+1]=dp[i+1][j]
            abcd abc* *代表一个或多个字符 dp[i+1][j+1]=dp[i][j+1]
            abcccc abc* *把前边一个也拿走 dp[i+1][j+1]=dp[i+1][j-1]                                   

至此，动态规划方程已经得到
同样第一行的初始化，代表s为""p只有为aA这样的才可以匹配。
而第一列的话，如果p为空的话是一定不能匹配的，所以默认为false.

代码：

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s==null||p==null)
            return false;
        boolean[][] dp=new boolean[s.length()+1][p.length()+1];//dp[i][j]表示以i-1为结尾位置的s子串和以j-1为结尾位置的p子串是否能够match
        dp[0][0]=true;
        for(int j=0;j<p.length();j++){//s取出子串为“”，如果p  1*2*3*这样子类型就能够匹配
            if(p.charAt(j)=='*'&&dp[0][j-1])
                dp[0][j+1]=true;
        }
        for(int i=0;i<s.length();i++){
            for(int j=0;j<p.length();j++){
                if(p.charAt(j)=='.'||p.charAt(j)==s.charAt(i)){
                    dp[i+1][j+1]=dp[i][j];    
                }
                else if(p.charAt(j)=='*'){
                    if(p.charAt(j-1)!='.'&&p.charAt(j-1)!=s.charAt(i)){//直接丢弃前边一个字符  a*之间被丢弃
                        dp[i+1][j+1]=dp[i+1][j-1];
                    }
                    else{
                    //aaa a*
                        dp[i+1][j+1]=dp[i+1][j]||dp[i+1][j-1]||dp[i][j+1];//abc abc* abcc* 
                        //a*          当做a        当做“”        当做多个a(注意这里不能是dp[i][j]这样的话就只是当做了一个a)
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}

第三题

[leetcode44]https://leetcode.com/problems/wildcard-matching/
同上题大同小异，这次"?"代表任意一个字符，"*"代表任意一个字符序列，可以为空。

方法一:dp解法

和上一题一样的思路，而且分析比上一题简单多，所以这里不再详述

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s==null||p==null)
            return false;
        boolean[][] dp=new boolean[s.length()+1][p.length()+1];
        dp[0][0]=true;
        for(int j=0;j<p.length();j++){
            if(p.charAt(j)=='*'&&dp[0][j])
                dp[0][j+1]=true;
        }
        for(int i=0;i<s.length();i++){
            for(int j=0;j<p.length();j++){
                if(p.charAt(j)==s.charAt(i)||p.charAt(j)=='?')
                    dp[i+1][j+1]=dp[i][j];
                else if(p.charAt(j)=='*'){
                    dp[i+1][j+1]=dp[i+1][j]||dp[i][j+1];
                    //            直接去除*   *代替一个或多个其他字符
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}

方法二：

由于这里和前边的元素没有关系了，所以如果前面出现了不匹配，那么直接就可以判定不匹配，不需要就行后边的操作，所以直观上，上述动态规划的方法就存在很大的时间浪费，这里看到一种更有效率的方法。本质思想就是遇到之后，你走不通了那么这一段走不通的都丢给*来代替。

public class Solution {
    public boolean isMatch(String str, String pattern) {
        if(str==null||pattern==null)
            return false;
        int s=0;
        int p=0;
        int match=0;//*所代表的范围的结尾
        int starIdx=-1;//*的位置
        while(s<str.length()){
            if(p<pattern.length()&&(pattern.charAt(p)=='?'||pattern.charAt(p)==str.charAt(s))){
                s++;
                p++;
            }
            else if(p<pattern.length()&&pattern.charAt(p)=='*'){
                starIdx=p;
                match=s;
                p++;//s不增加，因为有可能*代表空
            }
            else if(starIdx!=-1){
                p=starIdx+1;
                match++;
                s=match;
            }else{
                return false;
            }
        }
        while(p<pattern.length()&&pattern.charAt(p)=='*'){//如果后边都是*的话，可以当做什么也没有
            p++;
        }
        return p==pattern.length();
    }
}

题目四：

[leetcode97]https://leetcode.com/problems/interleaving-string/
给了三个字符串str1 str2 str3 str3是不是str1和str2的交叉

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1=s1.length();
        int len2=s2.length();
        int len3=s3.length();
        if(len1+len2!=len3)
            return false;
        boolean[][] dp=new boolean[len1+1][len2+1];//dp[i+1][j+1]表示s1[0,i] s2[0,j]时候满足条件交接到s3[0,i+j+1]
        dp[0][0]=true;
        for(int j=0;j<len2;j++){
            if(s2.charAt(j)==s3.charAt(j))
                dp[0][j+1]=true;
            else
                break;
        }
        for(int i=0;i<len1;i++){
            if(s1.charAt(i)==s3.charAt(i))
                dp[i+1][0]=true;
            else
                break;
        }
        char c1;
        char c2;
        char c3;
        for(int i=0;i<len1;i++){
            c1=s1.charAt(i);
            for(int j=0;j<len2;j++){
                c2=s2.charAt(j);
                c3=s3.charAt(i+j+1);
                if(c1==c3&&c2==c3)
                    dp[i+1][j+1]=dp[i][j+1]||dp[i+1][j];
                else if(c2==c3)
                    dp[i+1][j+1]=dp[i+1][j];
                else if(c1==c3)
                    dp[i+1][j+1]=dp[i][j+1];
            }
        }
        return dp[len1][len2];
    }
}

题目五

[leetcode115]https://leetcode.com/problems/distinct-subsequences/
一个字符串中包含多少个另一个字符串

public class Solution {
    public int numDistinct(String s, String t) {
        int len1=s.length();
        int len2=t.length();
        int[][] dp=new int[len1+1][len2+1];
        dp[0][0]=1;
        for(int i=0;i<len1;i++){
            dp[i+1][0]=1;
        }
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                if(s.charAt(i)==t.charAt(j)){
                    dp[i+1][j+1]=dp[i][j]+dp[i][j+1];
                }
                else
                    dp[i+1][j+1]=dp[i][j+1];
            }
        }
        return dp[len1][len2];
    }
}

public class Solution {
    public int numDistinct(String s, String t) {
        int len1=s.length();
        int len2=t.length();
        int[] dp=new int[len2+1];
        int prev;
        int cur;
        for(int i=0;i<len1;i++){
            dp[0]=1;
            prev=1;
            char c=s.charAt(i);
            for(int j=0;j<len2;j++){
                if(t.charAt(j)==c){
                    cur=dp[j+1]+dp[j];
                }
                else
                    cur=dp[j+1];
                dp[j]=prev;
                prev=cur;
            }
            dp[len2]=prev;
        }
        return dp[len2];
    }
}