我 太 弱 了

$f_{i,j}$ 当前已经考虑了前 $i$ 个字符，最末尾有 $j$ 个字符与串 $b$ 相同，最少需要修改多少个字符。

#include <cstdio>
#include <cstring>

char a[10001], b[1001];
int f[2][1001];
inline int min(int x, int y) {return x < y ? x : y;}

int main() {
	scanf("%s%s", a + 1, b + 1);
	int n(strlen(a + 1)), m(strlen(b + 1)), ans(0x7fffffff);
	memset(f[0], 0x3f, sizeof f[0]), f[0][0] = 0;
	for (int i(1); i <= n; ++ i) {
		int t(i & 1), t2(i - 1 & 1);
		memset(f[t], 0x3f, sizeof f[t]);
		f[t][0] = f[t2][0];
		for (int j(1); j <= min(m - 1, i); ++ j) {
			f[t][j] = (a[i] == b[j] ? f[t2][j - 1] : f[t2][j - 1] + 1);
			f[t][0] = min(f[t][0], f[t2][j]);
		}
		f[t][0] += a[i] == b[1];
	}
	for (int i(0); i < m; ++ i) ans = min(ans, f[n & 1][i]);
	printf("%d", ans);
}