通过Edit Distance问题理解动态规划算法

浏览数：19 / 时间：2015年06月08日

动态规划算法理解

动态规划（Dynamic Programming）是通过组合子问题的解来解决问题。所以对于一个问题是否能够用DP，就要看是否具有相同的子问题结构，而且计算有重叠。导致直接用递归来解决的话就带来巨大开销，甚至栈溢出，动态规划就是一种改进暴力递归的策略，有自顶向下和自底向上2个角度来看问题。Top-Down的话就是为了避免递归过程中的重复计算，会记录下中间步骤可以重复利用的子问题的解（所谓的“Memoization”）；而Down-Top是从最基本的情况来发掘相邻子问题的规律，从而使的子问题得到最优解，从而得到最终问题的解。比如看下面这个问题Edit Distance：

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

显然我们不能有什么妙招，只能对A,B字符串一个个字符的去看，但是有三种情况

1）A[0]和B[0]先判断，然后递归看 A[1..n] B[1....m]之间的最短编辑距离 ,n,m为A,B串的长度；

2）在A的开头插入B[0] ,然后看原始的字符串A[0...n]和B余下的串(B[1...m])之间的编辑距离；

3）在A的开头删去一个字符，然后看 A[1..n],B[0....m]之间的最短编辑距离；

递归的终止条件是：当A或者B为空的时候，就需要从一方转换为另一方。很容易写出下面的递归表达式：

转换为递归程序很容易，但是开销很大，画一个分支图很容易理解，联系求Fibonacci数列。

而采用自顶向下的方法，需要把子问题的解保存在容器中，在这里需要将中间的子串(s1,s2)对应的最小编辑距离保存在哈希表中，虽然比上述方法好点，但同样开销很大。

所以接下来看自底向上的思路：开辟一个矩阵Cost[N][M],其中N=A.length()+1, M = B.length()+1;其中Cost[i][j]表示从字符串A[0..i]转换为B[0...j]的最短编辑距离，最基本的情况就是矩阵的第一行和第一列，表示由一个空串向对方转换，显然编辑距离就是对方的长度。接下来看其他位置Cost[i][j]的候选情况有三种：从左上角达到，表示A B各增加一个字符；从上面一个位置得到，表示A增加一个字符；从左边一个位置达到，表示B增加一个字符，所以取三者中最小值即可。

public int minDistance(String word1, String word2) {
if (word1 == null && word2 == null)
return 0;
if (word1 == null || word1.isEmpty())
return word2.length();
if (word2 == null || word2.isEmpty())
return word1.length();
int m = word1.length();
int n = word2.length();

    // Cost[i][j]表示words1.substr(0, i)到 words2.substr(0, j) 的最短编辑距离
    int[][] Cost= new int[m+1][n+1];
    // 初始化边界情况
    for (int i = 0; i <= m; ++i) 
     Cost[i][0] = i;
    for (int j = 0; j <= n; ++j) 
     Cost[0][j] = j;
    
    // 由A[0...i]到B[0...j]的最短距离分为三种情况
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
         int insertBoth = Cost[i-1][j-1] + replaceCost(word1, word2,0,0);
         int insertA = Cost[i-1][j] + 1;
         int insertB = Cost[i][j-1] + 1;
            Cost[i][j] = Math.min(Math.min(insertA, insertB), insertBoth);
        }
    }

    return Cost[m][n];
  }
private int replaceCost(String word1, String word2, int i1, int i2) {
return word1.charAt(i1) == word2.charAt(i2) ? 0 : 1;
}

参考：

（1）算法导论

（2）Leetcode Discuss