Let `dp(i, j)`

be the answer for strings `A[i:]`

and `B[j:]`

. Let's try to compute it by a top-down dp:

- When
`i == len(A) or j == len(B)`

, one of the strings is empty, so the answer is just the sum of the remaining lengths. - When
`A[i] == B[j]`

, the answer is just`dp(i+1, j+1)`

. For example, when evaluating the distance between "acai" and "apple", we only need to look at the distance between "cai" and "pple". - When
`A[i] != B[j]`

, then they both cannot be in the final word, so we either delete`A[i]`

or`B[j]`

. Thus, our answer is`1 + min(dp(i+1, j), dp(i, j+1))`

.

```
def minDistance(self, A, B):
memo = {}
def dp(i, j):
if (i, j) not in memo:
if i == len(A) or j == len(B):
ans = len(A) + len(B) - i - j
elif A[i] == B[j]:
ans = dp(i+1, j+1)
else:
ans = 1 + min(dp(i+1, j), dp(i, j+1))
memo[i, j] = ans
return memo[i, j]
return dp(0, 0)
```

We could have also attempted a bottom-up DP, as shown below.

```
def minDistance(self, A, B):
M, N = len(A), len(B)
dp = [[0] * (N+1) for _ in xrange(M+1)]
for i in xrange(M):
dp[i][-1] = M-i
for j in xrange(N):
dp[-1][j] = N-j
for i in xrange(M-1, -1, -1):
for j in xrange(N-1, -1, -1):
if A[i] == B[j]:
dp[i][j] = dp[i+1][j+1]
else:
dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1])
return dp[0][0]
```