51nod 编辑距离 + 滚动数组优化

这道题一开始觉得增加和删除会移动字符串的位置很不好做

两个字符串dp状态一般是第一个前i个和第二个前j个

#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 1123;
char a[MAXN], b[MAXN];
int f[MAXN][MAXN];int main()
{scanf("%s%s", a + 1, b + 1);int n = strlen(a + 1), m = strlen(b + 1);REP(i, 0, n + 1) f[i][0] = i;REP(i, 0, m + 1) f[0][i] = i;REP(i, 1, n + 1)REP(j, 1, m + 1){if(a[i] == b[j]) f[i][j] = f[i-1][j-1];else f[i][j] = min(f[i-1][j], min(f[i][j-1], f[i-1][j-1])) + 1;}printf("%d\n", f[n][m]);return 0;
}

这里的转移只和上一行有关
所以可以用滚动数组优化空间
处理过的就是这一行，没处理过的就是上一行

#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 1123;
char a[MAXN], b[MAXN];
int f[MAXN];int main()
{scanf("%s%s", a + 1, b + 1);int n = strlen(a + 1), m = strlen(b + 1);REP(i, 1, m + 1) f[i] = i;REP(i, 1, n + 1){int last = i - 1; //f[i-1][0] = i - 1f[0] = i;  //f[i][0] = iREP(j, 1, m + 1){int temp = f[j]; if(a[i] == b[j]) f[j] = last; //last = f[i-1][j-1]else f[j] = min(f[j], min(f[j-1], last)) + 1;last = temp;}}printf("%d\n", f[m]);return 0;
}