题意：你可以对字符串s进行3种操作：
1，在pos位置插入字符ch。
2，删除pos位置的字符。
3，替换pos位置的字符为ch。
问最少需要多少次操作可以把字符s变成字符s1?
思路：
设dp[i][j]为字符串s的前i个字符替换成s1的前j个字符的最小花费。则有三种转移：
1：dp[i - 1][j - 1] + (s[i] != s1[j]) -> dp[i][j] //将s[i]替换为s1[j] （真实位置是j）。
2：dp[i - 1][j] + 1 ->dp[i][j] //删除i位置的数(对应真实的s的位置是j + 1, 因为这个转移相当于s的前i - 1字符已经变成s1的前j个字符，所以删除的是第j + 1个位置的字符）。
3：dp[i][j - 1] + 1 -> dp[i][j] //在i位置后面添加一个数（真实位置是j）。
代码：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1010;
char s[maxn], s1[maxn];
int dp[maxn][maxn];
void print(int i, int j, int remain) {
if(!remain) return;
if(i > 0 && j > 0 && dp[i - 1][j - 1] + (int)(s[i] != s1[j]) == dp[i][j]) {
print(i - 1, j - 1, remain - (int)(s[i] != s1[j]));
if(s[i] != s1[j]) printf("REPLACE %d %c
", j, s1[j]);
} else if(i > 0 && dp[i - 1][j] + 1 == dp[i][j]) {
print(i - 1, j, remain - 1);
printf("DELETE %d
", j + 1);
} else if(j > 0 && dp[i][j - 1] + 1 == dp[i][j]) {
print(i, j - 1, remain - 1);
printf("INSERT %d %c
", j, s1[j]);//j位置插入s1[j]
}
}
int main() {
scanf("%s", s + 1);
scanf("%s", s1 + 1);
int n = strlen(s + 1), m = strlen(s1 + 1);
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++) dp[i][0] = i;
for (int i = 1; i <= m; i++) dp[0][i] = i;
dp[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (int)(s[i] != s1[j]));
dp[i][j] = min(dp[i][j], min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
}
printf("%d
", dp[n][m]);
print(n, m, dp[n][m]);
}