动态规划思考路径：
1、根据题目所给的条件和目标，构造问题
2、拆解子问题，即定义状态
3、求解简单子问题，判断是否有可以直接求解的子问题。通常是dp数组的初始化
4、通过已知问题求解，即构造状态转移方程
5、判断复杂度是否在千万级别内，如果超过则超时
一、构造问题
根据题意，本题的目标为：给你两个单词 word1 和 word2，将word1转换为word2，并求出转换所需的最小次数。
二、将所给条件缩小，拆解为子问题
我们以示例一为例：
题目要求我们将字符串“horse”转换为“ros”，乍一看或许没什么思路。我们定义lena和lenb分别为两个字符串的长度，那么求解Question(lena - 1, lenb - 1)，Question(lena , lenb - 1)，Question(lena - 1, lenb)就是缩小条件后的子问题，Question(0, 0)就是最小的子问题。
动态规划的核心思想就在于当前问题可以由子问题的状态推导而来。
我们进而将所有的问题列举出来，形成一个二维矩阵：
那么dp[i][j]所表示的就是word1前i个字符转换为word2前j个字符所需要的最少的操作次数。
三、求解简单子问题，判断是否有可以直接求解的子问题。通常是dp数组的初始化
通过观察，当word1为空时，word1所转换为word2的字串所需要的最小的操作次数即为word2字串的长度。所以我们如此初始化：
初始化：
dp[i][0] = i：将 word1的前i个字符转换为空字符串 word2[0]，需要i次删除操作。dp[0][j] = j：将空字符串 word1[0]转换为 word2的前j个字符，需要j次插入操作。
四、通过已知问题求解，即构造状态转移方程
题目要求我们可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
对于word1：
1、如果 word1[i] == word2[j]，则 dp[i][j] = dp[i-1][j-1]，即当前字符相等，直接从前一个状态dp[i-1][j-1]的转化来，不需要任何额外操作。
2、如果 word1[i] != word2[j]，则 dp[i][j] 可以从以下三种操作中选择最小值：
- 如果选择插入操作，即从状态dp[i][j-1]转化到dp[i][j]，此时dp[i][j] = dp[i][j-1] + 1。
- 如果选择删除操作，即从状态dp[i-1][j]转化到dp[i][j]，此时dp[i][j] = dp[i-1][j] + 1。
- 如果选择替换操作，此时无需关心word1[i]和word2[j]，相当于word1和word2各删除一个字符，即从状态dp[i-1][j-1]转化到dp[i][j]，此时dp[i][j] = dp[i-1][j-1] + 1。
注： 对于word1
dp[i-1][j-1] + 1：替换字符word1[i]为word2[j]。dp[i-1][j] + 1：删除字符word1[i]dp[i][j-1] + 1：插入字符word2[j]到word1。(也相当于word2字符串删除word2[j]，但本题的分析是基于word1字符串的。)
完整代码：
【小技巧】：在动态规划问题中，为 dp 数组多设置一行一列可以简化边界条件的处理，避免了在状态转移时对边界情况的特殊处理。通过在字符串开头增加一个字符（通常是空字符），可以使 dp 数组的下标与字符串的下标一一对应，从而简化代码逻辑。
class Solution {
public:
int minDistance(string word1, string word2) {
// 首先拆解子问题：
// word1前i个字符 如何转换成 word2前i个字符，所使用的最少操作次数
// 四种状态
// 1、什么也不做，word1 == word2
// 2、第i步为插入一个字符后，转换成word2的最少操作数
// 3、第i步为删除一个字符后。。。
// 4、第i步为替换一个字符后。。。
string str1 = " " + word1;
string str2 = " " + word2;
int len1 = str1.size(), len2 = str2.size();
vector<vector<int>> dp(len1, vector<int>(len2, 0));
for(int i = 0; i < len1; i++)
{
for(int j = 0; j < len2; j++)
{
if(i == 0){
dp[i][j] = j;
}else if(j == 0){
dp[i][j] = i;
}else if(str1[i] == str2[j]){
dp[i][j] = dp[i - 1][j - 1];
}else{
dp[i][j] = min(dp[i - 1][j - 1]/*替换*/, min(dp[i - 1][j]/*删除*/, dp[i][j - 1]/*插入*/)) + 1;
}
}
}
return dp[len1 - 1][len2 - 1];
}
};