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

动态规划算法理解

     动态规划(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






  

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。