！！！题解 | 编辑距离(一) 没思路的一道 注意这里的下标多开 可以防止手动进行分支控制

tip：
因为字符串下标从 0 开始，所以 word1 的第 i 个字符在代码中对应的下标是 i-1，word2 的第 j 个字符对应 j-1。
为了让 DP 数组的下标和字符串的下标完美对齐（即 dp[i][j] 直接对应 word1[i] 和 word2[j]），
很多高手会在字符串前面加一个“哨兵”（空格或任意占位符），让真实的字符串从下标 1 开始
#include <algorithm>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    int editDistance(string str1, string str2) {
        // write code here
        /*其实和那个求字符串的最长公共子序列是差不多的套路。
        当前字符串1，它的下标是I；字符串2它的下标是J。不管i，j他们在什么位置，当前元素就是他们两个。
        如果I和J他们两个相等，那么就求让字符串1的前I-1个字符，与字符串2的前j-1个字符让他们两个变得相等，需要的操作数。
        第2种情况，如果I不等于J，让字符串1的I去，变成字符串2的J，就是做了一次修改操作，再加上前I-1和前J-1子串让他们相同，需要的操作数。
        还有一种情况就是I和J既然不相等，我就在字符串1的I后面加入一个插入一个与J相等的数，那这时候他们是不是就相等了，这时候下标i+1与j相等了，所以这时候要求的就是字符串1的前i个数，与字符串2的前j-1个数，让它们相同需要的操作数
        第3种情况呢，我们这时候可以试探，假设i前面的那个数i-1正好和J相等，这样我们就删掉I，让字符串1的前-1个字符与字符串2的前j个字符，让它们变得相同需要的操作数。
        */
        //递归很好写，这里用迭代法。
        //下标从1开始。
        int len1=str1.size();
        int len2=str2.size();
        //它们谁等于0都不能直接返回，依旧有的处理
        vector<vector<int>> dp(len1+1,vector<int>(len2+1));
        for(int i=0;i<=len1;i++){
            dp[i][0]=i;//把str1变成空
        }
        for(int j=0;j<=len2;j++){
            dp[0][j]=j;//把空变成str2
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(str1[i-1]==str2[j-1])dp[i][j]=dp[i-1][j-1];
                else{
                    dp[i][j]=min(dp[i-1][j], min(dp[i][j-1],dp[i-1][j-1]))+1;
                    //不行 std::min 只能比较两个值。如果你想比较三个数，需要嵌套使用 min
                }
            }
        }
        return dp[len1][len2];
    }
};