常用算法思想之动态规划的后缀思想

思路:后缀是指要解决的子问题是原问题的后半部分，如果用字符串类描述，相当于子问题永远都是原问题的后半部分 str[i:]

str[i:] 表示从下标i开始，一直到末尾的整个字符串

示例

最长公共子序列长度

给定两个字符串A:HIEROGLYPHOLOGY 和字符串B:MICHAELANGELO,他们最长公共的子序列为

HIEROGLYPHOLOGY <--> MICHAELANGELO

可以得到最长公共子序列长度为5。分析如下:

• A、B两个字符串，如果字符串A的第一个字符和B的第一个字符一模一样，那这个字符一定是属于最长子序列的一个，剩余部分为A[1:]和B[1:]，且最终结果就是在前一个结果的基础上加上剩余部分最长字串长度即可
• A、B两个字符串，如果第一个字符不一样，最长公共子序列要么包含A中的第一个字符、要么包含B中的第一个字符、或者是两个都不是。即最长公共字串要么你是 A[1:]和B[0:],要么是A[0:]和B[1:]，所以最长公共字串就是 A[1:]和B[0:]，A[0:]和B[1:]之间的最大值

最终要计算的结果是 dp(A.length()-1,B.length()-1)。即字符串A和字符串B的最长公共子序列长度。 假设输入的字符串A是 HIE B是 MCHI，目标就是要计算dp(2,3)

2表示A字符串的最后一个下标，3表示B字符串的最后一个下标

横坐标表示字符串A中参与计算最长公共子序列长度的最后一个字符；纵坐标表示字符串B中参与计算最长公共子序列长度的最后一个字符

1. 先比较A和B的第一个字符，看不相等，执行不相等的逻辑，所以最大公共子序列要么在A[1:]和B[0:],要么在A[0:]和B[1:]，要么在A[1:]和B[1:]

x 表示剩余需要比较的子字符开始的位置

1. 以 A[1:]和B[0:] 为例，首字母仍然不一样，此时最大公共子序列要么在 A[2:]B[0:]、要么在A[1:]和B[1:]

• 表示当前图表中没有写这个分支，只看挑选的分支执行路径

1. 以A[1:]和B[1:]为例，首字母仍然不一样，它的最长字串就是A[1:]B[2:]或者是A[2:]B[1:],考虑到这只是个子串，那最终在计算分别以下标1结尾的字符串A和B的最长公共字串中，需要看前面的结果A[1]B[0]和A[0]B[1]的最大值是那个，因而必须先计算出A[0]b[1]才能确定它的取值

1. 以A[1:]B[2:]为例，A[1]和B[2]不相等，它需要计算的 最长子序列就是A[1:]B[3:]或者是A[2]B[2]，同样的要计算A中以1结尾的字串和B中以2结尾的字串的最大子序列长度，先要看下A[0]B[2]的值

1. 以A[1:]B[3:]为例，A[1]和B[3]一样，但是需要去计算A[0]B[3]

从上面的分析过程可以看到，要计算对应的位置的值，必须先把它之前的值都准备好，才能继续进行，也就是说，如果之前已经计算过，就可以利用它继续计算，否则只能回过头来再计算一遍，这样也不划算，既然如此，就可以按照从横坐标0开始，一行一行的填充数据。

当A取下标0的时候，就是只有1个字母和整个B字符串去对比，当A取下标1的时候，就是A[0:1]去和B对比，对应的操作顺序如下

显示按照蓝线，然后是绿线最后是黄线，然后计算出值。

   public int longestCommonSubsequence(String A, String B) {
        // 特殊情况直接返回
        if(A==null || "".equals(A) || B==null || "".equals(B)){
            return 0;
        }
        int length=0;
        int [][] arr=new int[A.length()+1][B.length()+1];
        //从1开始是因为只要当前有一个是一样的，后面的至少和他保持一致，最长序列不会比它少，如果从0开始，那么需要有额外的逻辑去保证第0行的正确性，而从1开始就可以很好的利用现有的逻辑，不必写过多的冗余代码
        for(int i=1;i<=A.length();i++){
           for(int j=1;j<=B.length();j++){
               if(A.charAt(i-1)==B.charAt(j-1)){
                   arr[i][j]=arr[i-1][j-1]+1;
               }else{
                   arr[i][j]=Math.max(arr[i-1][j],arr[i][j-1]);
               }
               
           }
        }
        return arr[A.length()][B.length()];
        
    }

编辑距离

给两个字符串 word1 和 word2,找到最少的步骤，使得word1能够变成word2,可以使用的操作包括

• 插入一个字符
• 删除一个字符
• 替换一个字符

比如 "mart" 变成 "karma" 最少需要3步。分析如下 从上面的最长公共字串思想，可以类比，要使一个字串变成另外一个字串，根据提供的3中操作方式，分别要去这三种可能性的最小值。假定给的字符串是A和B，A要变成B，首先从第一个字符开始

• A的第一个字符变成B的第一个字符，或者B的第一个字符变成A的第一个字符，达到条件 ，如果 A[0]==B[0],不需要变更dp[0,0]=dp[-1,-1]，否则 dp[0,0]=dp[-1,-1]+1
• 删掉A的第一个字符，再观察剩下的,dp[0,0]=dp[-1,0]
• 删除B的第一个字符，再观察剩下的,dp[0,0]=dp[0,-1]

同样用dp表示从第0个下标开始，需要计算的最小值上面三种情况的最小值，数组本身是从0开始的，那从-1开始就代表一个字符都没有，显然这样的编辑距离就是另外一个有的长度，这也就使得初始值被建立，最终得到的程序如下

 public int minDistance(String word1, String word2) {
        
        // write your code here
        if(null == word1 || null == word2){
           return 0;
        }
        
        int[][] arr=new int[word1.length()+1][word2.length()+1];
        for(int i=0;i<=word1.length();i++){
            arr[i][0]=i;
        }
        for(int j=1;j<=word2.length();j++){
            arr[0][j]=j;
        }
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                   arr[i][j]=Math.min(Math.min(arr[i][j-1]+1,arr[i-1][j]+1),arr[i-1][j-1]); 
                }else{
                  arr[i][j]=Math.min(Math.min(arr[i][j-1]+1,arr[i-1][j]+1),arr[i-1][j-1]+1);  
                }
            }
        }
        return arr[word1.length()][word2.length()];
    }