算法竞赛模板

链接
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

dp[i][j] 表示使第一个单词[1,i]个字母和第二个单词[1,j]个字母相互匹配所花费的代价

可以从几种状态转移过来

1. 如果s1[i] == s2[j] ,那么一定从dp[i-1][j-1]花费0的代价转移过来最优
2. 不等于分成几种可能的转移情况
   替换s1的第i个字符，这样代价是dp[i-1][j-1] + 1
   删掉s1的第i个字符，代价dp[i-1][j] + 1
   s1尾部增加一个字符，代价dp[i][j-1] + 1

滚动数组优化

class Solution {
public:
    int minDistance(string& s1, string& s2) {
        int n = s1.size(),m = s2.size();
        s1 = '0' + s1,s2 = '1' + s2;
        int dp2[m+1];
        int leftup = 0,backup;
        for(int i = 0; i <= m; i++) dp2[i] = i;
        for(int i = 1; i <= n; i++) {
            dp2[0] = i;
            leftup = i - 1;
            for(int j = 1; j <= m; j++) {
                backup = dp2[j];
                if(s1[i] == s2[j]) {
                    dp2[j] = leftup;
                } else {
                    dp2[j] = min(dp2[j - 1] + 1, dp2[j] + 1);
                    dp2[j] = min(leftup + 1, dp2[j]);
                }
                leftup = backup;
            }
        } 
        return dp2[m];
    }
};