solution.md

# 编辑距离

<p>给你两个单词 <code>word1</code> 和 <code>word2</code>，请你计算出将 <code>word1</code> 转换成 <code>word2</code><em> </em>所使用的最少操作数 。</p><p>你可以对一个单词进行如下三种操作：</p><ul>	<li>插入一个字符</li>	<li>删除一个字符</li>	<li>替换一个字符</li></ul><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>word1 = "horse", word2 = "ros"<strong><br />输出：</strong>3<strong><br />解释：</strong>horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>word1 = "intention", word2 = "execution"<strong><br />输出：</strong>5<strong><br />解释：</strong>intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>0 <= word1.length, word2.length <= 500</code></li>	<li><code>word1</code> 和 <code>word2</code> 由小写英文字母组成</li></ul>

以下程序实现了这一功能，请你填补空白处的内容：

```cpp
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
	int minDistance(string word1, string word2)
	{
		int l1 = word1.length();
		int l2 = word2.length();
		vector<int> dp(l2 + 1);
		for (int i = 0; i <= l2; i++)
		{
			dp[i] = i;
		}
		int up = 0;
		for (int i = 1; i <= l1; i++)
		{
			int left_up = dp[0];
			dp[0] = i;
			for (int j = 1; j <= l2; j++)
			{
				up = dp[j];
				_________________________;
				else
				{
					dp[j] = 1 + min(left_up, min(up, dp[j - 1]));
				}
				left_up = up;
			}
		}
		return dp[l2];
	}
};
```

## template

```cpp
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
	int minDistance(string word1, string word2)
	{
		int l1 = word1.length();
		int l2 = word2.length();
		vector<int> dp(l2 + 1);
		for (int i = 0; i <= l2; i++)
		{
			dp[i] = i;
		}
		int up = 0;
		for (int i = 1; i <= l1; i++)
		{
			int left_up = dp[0];
			dp[0] = i;
			for (int j = 1; j <= l2; j++)
			{
				up = dp[j];
				if (word1[i - 1] == word2[j - 1])
				{
					dp[j] = left_up;
				}
				else
				{
					dp[j] = 1 + min(left_up, min(up, dp[j - 1]));
				}
				left_up = up;
			}
		}
		return dp[l2];
	}
};
```

## 答案

```cpp
if (word1[i - 1] == word2[j - 1])
{
	dp[j] = left_up;
}
```

## 选项

### A

```cpp
if (word1[i + 1] == word2[j + 1])
{
	dp[j] = left_up;
}
```

### B

```cpp
if (word1[i] == word2[j])
{
	dp[j] = left_up;
}
```

### C

```cpp
if (word1[i - 1] == word2[j - 1])
{
	dp[j] = left_up + 1;
}
```