# Leetcode 72 - Edit distance

`Note`

`dp`

question.`dp[i][j]`

means the`min operations`

to convert`word1 [0, i-1]`

to`word2 [0, j-1]`

. (Techinique we used before: iterate from`i=1`

and`j=1`

)- How to initialize
`dp[i][0]`

and`dp[0][j]`

? We can’t just initialize them all to`0`

.`dp[i][0]`

means the min operations to convert`word1 [0, i-1]`

to an empty string. So, apparently,`dp[i][0] = i`

. Likewise,`dp[0][j] = j`

. - For dp deduction, there are
`2`

situations:- When
`word1[i-1] === word2[j-1]`

, these 2 chars are the same, so`dp[i][j] = dp[i-1][j-1]`

- When
`word1[i-1] !== word2[j-1]`

, there arekinds of operations:`3`

- Replace:
`dp[i][j] = dp[i-1][j-1] + 1`

- Add/Delete: Convert
`word1 [0, i-2]`

to`word2 [0, i-1]`

or vice versa.`dp[i][j-1] + 1`

Or`dp[i-1][j] + 1`

. When to convert a longer one to a short one, it’s`deletion`

. In the reverse way, it’s`addition`

.

- Replace:

- When

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

- Insert a character
- Delete a character
- Replace a character

**Example**

1 | Input: word1 = "horse", word2 = "ros" |

1 | /** |