Below is my recursive solution with running time ~160 ms

```
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
def _dp(x, y):
if distance[x][y] is None:
if x == 0:
# boundary condition
distance[x][y] = y
elif y == 0:
# boundary condition
distance[x][y] = x
elif word1[x-1] == word2[y-1]:
distance[x][y] = _dp(x-1, y-1)
else:
distance[x][y] = min(_dp(x-1, y), _dp(x, y-1), _dp(x-1, y-1)) + 1
return distance[x][y]
len1, len2 = len(word1), len(word2)
distance = [[None] * (len2+1) for _ in range(len1+1)]
return _dp(len1, len2)
```

And this is the standard DP version, with running time 268 ms. Why the recursive solution is much faster than the non-recursive one?

```
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
len1, len2 = len(word1) + 1, len(word2) + 1
distance = [[0] * len2 for _ in range(len1)]
'''
Define D(i, j) as the edit distance between W1[0 : i] and W2 [0 : j],
i.e., the first i/j characters of W1 and W2, respectively
The edit distance between W1 and W2 is thus D(n, m)
Base conditions:
D(i, 0) = i; D(0, j) = j
DP formula:
/ delete: D(i-1, j) + 1
D(i, j) = min -- insert: D(i, j-1) + 1
\ replace: D(i-1, j-1) + 0, if W1[i] == W2[j]
1, if W1[i] != W2[j]
'''
for x in xrange(1, len1):
distance[x][0] = x
for y in xrange(1, len2):
distance[0][y] = y
for x in xrange(1, len1):
for y in xrange(1, len2):
if word1[x-1] == word2[y-1]:
distance[x][y] = distance[x-1][y-1]
else:
distance[x][y] = min(distance[x-1][y], distance[x][y-1], distance[x-1][y-1]) + 1
return distance[-1][-1]
```