原题
思路：
利用二维数组dp[i][j]存储状态： 从字符串A的0~i位子字符串 到 字符串B的0~j位子字符串，最少需要几步。（每一次删增改都算1步）
所以可得边界状态dp[i][0]=i，dp[0][j]=j。
以及状态转移方程
即当比较 word1[i] 和 word2[j] 字符 相等 时，所需步数与 word1[i-1] 和 word2[j-1] 相等。
状态转移方程为：dp[i][j]=dp[i-1][j-1]
否则，状态转移方程为dp[i][j]= min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
class Solution
{
public:
int minDistance(string word1, string word2)
{
int oneSize = word1.size() + 1;
int twoSize = word2.size() + 1;
int dp[oneSize][twoSize] = {0};
for (int i = 0; i < oneSize; i++)
dp[i][0] = i;
for (int j = 0; j < twoSize; j++)
dp[0][j] = j;
for (int i = 1; i < oneSize; i++)
{
for (int j = 1; j < twoSize; j++)
{
int temp;
if (word1[i - 1] == word2[j - 1])
{
dp[i][j] = dp[i - 1][j - 1];
}
else
{
temp = min(dp[i - 1][j], dp[i][j - 1]);
dp[i][j] = min(dp[i - 1][j - 1], temp) + 1;
}
}
}
return dp[oneSize - 1][twoSize - 1];
}
};
