# 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:

- replace word1[pos1] with word1[pos2], or vise versa
- delete word1[pos1] from word1
- 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:

- Termination condition of Top Down DFS solution to initialization status of Bottom Up Dynamic Programming.
- 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];
}
```