题解 | #计算字符串的编辑距离# 带滚动数组内存优化

这道题的滚动数组因为需要参考值，和背包等问题还蛮不一样的，记一下

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string s1,s2;
    //最大公共子序列问题变种，代表替换几次可以使更短为更长的子序列
    cin>>s1>>s2;

    vector<vector<int>> dp(2,vector<int>(s2.size()+1));
    int i,j,curi,previ;

    //注意，ij代表长度而不是下标

    dp[0][0]=0;
    for(int j=0;j<=s2.size();++j){
        dp[0][j]=j;
    }

    for(i=1;i<=s1.size();++i){
        curi=i%2;
        previ=(i-1)%2;
        dp[curi][0]=i;//不同于其他滚动数组优化问题，这里要给每次第0行参考值，代表空字符串到另一个字符串的距离
        for(j=1;j<=s2.size();++j){
             dp[curi][j]=min({dp[previ][j-1]+(s1[i-1]!=s2[j-1]),dp[curi][j-1]+1,dp[previ][j]+1});
             //是否换，变后增，先删再变，三选一
             //坑1，i和j代表位数，如果要当字符串的下标要-1！
             //坑2，即使当前位相同，（不）替换操作也没有更高的优先级，也要参与总的比较
           
        }

    }
    
  cout<<dp[curi][s2.size()]<<endl;

}
// 64 位输出请用 printf("%lld")