20 Nov 2016

Recursion to 2 dimensional dynamic programing I

文章欢迎转载,但转载时请保留本段文字,并置于文章的顶部
Author: derek0883@gmail.com
本文原文地址:http://www.gorecursion.com/algorithm/2016/11/20/2d-dynamic1.html

This article will show you how to use recursion method solve problem, then easily lead to a 2 dimensional dynamic programing solution.

Edit Distance

Leetcode 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 

Video explanation

DFS O(3^n) time complexity solution

It already said you have 3 options, for string word1 and word2, So we start from index 0, pos1=0, pos2=0 if (word1.charAt(pos1) == word2.charAt(pos2)), just move pos1 and pos2 to the next. other wise, we have 3 options:

  1. replace word1[pos1] with word1[pos2], or vise versa
  2. delete word1[pos1] from word1
  3. delete word2[pos2] from word2
int dfs(String word1, int pos1, String word2, int pos2) {
    if (pos1 == word1.length() && pos2 == word2.length())
        return 0;
    if (pos1 == word1.length())
        return word2.length() - pos2;   
    if (pos2 == word2.length())
        return word1.length() - pos1;

    if (word1.charAt(pos1) == word2.charAt(pos2))
        return dfs(word1, pos1+1, word2, pos2+1);

    int opt1 = dfs(word1, pos1+1, word2, pos2+1) + 1;
    int opt2 = dfs(word1, pos1, word2, pos2+1) + 1;
    int opt3 = dfs(word1, pos1+1, word2, pos2) + 1;
    return Math.min(Math.min(opt1, opt2), opt3);
}

DFS+memorize O(m x n) solution

From recursion tree, we can see that in DFS solution we are repeatedly compute for same sub-problem. so memorizing will reduce time complexity to O(m x n), once the cache was filled, It just takes O(1) time to get the answer which already computed.

int dfsCache(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();

    int[][] cache = new int[m+1][n+1];
    for (int i = 0; i <= m; i++)
        Arrays.fill(cache[i], -1);
    return dfsCache(word1, 0, word2, 0, cache);
}
int dfsCache(String word1, int pos1, String word2, int pos2, int[][] cache) {
    if (pos1 == word1.length() && pos2 == word2.length())
        return 0;
    if (pos1 == word1.length())
        return word2.length() - pos2;   
    if (pos2 == word2.length())
        return word1.length() - pos1;

    if (cache[pos1][pos2] != -1)
        return cache[pos1][pos2];
    int min;
    if (word1.charAt(pos1) == word2.charAt(pos2)) {
        min = dfsCache(word1, pos1+1, word2, pos2+1, cache);
    } else {
        int opt1 = dfsCache(word1, pos1+1, word2, pos2+1, cache);
        int opt2 = dfsCache(word1, pos1, word2, pos2+1, cache);
        int opt3 = dfsCache(word1, pos1+1, word2, pos2, cache);
        min = Math.min(Math.min(opt1, opt2), opt3) + 1;
    }
    cache[pos1][pos2] = min;
    return cache[pos1][pos2];
}

DP O(m x n) time complexity solution

Almost every Top down + memorize solution can be converted to a Bottom Up Dynamic Programming solution. Just do the following changes:

  1. Termination condition of Top Down DFS solution to initialization status of Bottom Up Dynamic Programming.
  2. Optional condition of Top Down DFS solution to the formula of Bottom Up Dynamic Programming.
int dp(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();

    int[][] fn = new int[m+1][n+1];
    for (int i = 1; i <= m; i++)
        fn[i][0] = i;
    for (int j = 1; j <= n; j++)
        fn[0][j] = j;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i-1) == word2.charAt(j-1))
                fn[i][j] = fn[i-1][j-1];
            else {
                int min = Math.min(fn[i-1][j], fn[i][j-1]);
                fn[i][j] = Math.min(fn[i-1][j-1], min) + 1;
            }
        }
    }
    return fn[m][n];
}