动态规划dp函数 + 记忆数组

  • 算法思路
    先定义状态，匹配与不匹配两种。当不匹配时，有三种选择: 插入，删除，替换。
    dp(i, j)为str1[0...i]和str2[0..j]字符串为了匹配做出的代价。
    对于给定的字符串str1，str2，从右到左，即自顶向下进行匹配。会出现两种情况：
    • 当前字符匹配时，dp(i, j)沿用dp(i-1, j-1)的代价。
    • 当前字符不匹配时，有三种选择。
      dp(i, j-1) + 插入的代价
      dp(i-1, j) + 删除的代价
      dp(i-1, j-1) + 替换的代价
      当我们每个选择在向下递归时，只有三种选择，第一个选择结束又返回，进行第二个选择时，必定存在某个选择在当前字符被递归过的情况，因此我们可以利用记忆数组来减少重复的计算。 
import java.util.*;
public class Solution {
    //记忆数组来减少递归次数
    int[][] memory;
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {

        int len1 = str1.length();
        int len2 = str2.length();

        memory = new int[len1+1][len2+1];
        //初始化记忆数组
        for(int i = 0; i <= str1.length(); i++){
            for(int j = 0; j <= str2.length(); j++){
                memory[i][j] = -1;
            }
        }
        //自顶向下递归
        return dp(str1, str2, len1, len2, ic, dc, rc);
    }

    /**
    * dp函数
    */
    public int dp(String str1, String str2, int i, int j, int ic, int dc, int rc) {
        //利用记忆数组直接返回
        if(memory[i][j] != -1)
            return memory[i][j];
        if(i == 0) // str1先走完，只能插入str2还没比较过的字符了
            return memory[i][j] = j*ic;
        if(j == 0) // str2先走完， 只能删除str1还没比较过的字符了
            return memory[i][j] = i*dc;
        if(str1.charAt(i-1) == str2.charAt(j-1)) //如果当前字符相等， 直接向前比较
            memory[i][j] = dp(str1, str2, i-1, j-1, ic, dc, rc);
        else{ //比较哪个动作的代价最小
            memory[i][j] = Math.min(Math.min(dp(str1, str2, i, j-1, ic, dc, rc)+ic, dp(str1, str2, i-1, j, ic, dc, rc)+dc), dp(str1, str2, i-1, j-1, ic, dc, rc)+rc);
        }
        return memory[i][j];
    }
}
  • 算法复杂度
    • 时间:O(2^N)。自顶向下的递归深度。
    • 空间:O(N*M)。二维数组的空间。

递推 dp数组

  • 算法思路
    可以用递推的解法，dp数组的含义跟dp函数一样，不同的是，dp数组采用的是自底向上的解法，递归采用的是自顶向下的解法。 
import java.util.*;

public class Solution {
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here
        int n = str1.length(), m = str2.length();
        int[][] dp = new int[n+1][m+1];
        for(int i = 1; i <= n; i++){
           dp[i][0] = i*dc; 
        }
        for(int j = 1; j <= m; j++){
           dp[0][j] = j*ic;
        }
        for(int i = 1; i <= n; i++){
           for(int j = 1; j <= m; j++){
               if(str1.charAt(i-1) == str2.charAt(j-1))
                   dp[i][j] = dp[i-1][j-1];
               else
                   dp[i][j] = min(dp[i-1][j]+dc, dp[i][j-1]+ic, dp[i-1][j-1]+rc);
            }
        }
        return dp[n][m];
    }

    public int min(int a, int b, int c){
        return Math.min(a, Math.min(b, c));
    }
}
  • 算法复杂度
    • 时间复杂度:O(N*M)。其中 m 为 str2 的长度，n 为 str1的长度。
    • 空间复杂度: O(N*M)。二维数组的空间。