这个题也做到过,貌似是鹅厂的压轴题,用三种方式编辑两个字符串的相似距离。
题目
集合:将a[1~ j]变成b[1~ j]的操作方式
属性:min
考虑过程比较难,从末尾开始考虑,三种操作方式上着手。
以下来自AcWing网友整理,很细致
有三种操作,所以有三个子集
ok子集划分完了
考虑状态转移的时候
先考虑如果我没有进行这个操作应该是什么状态
然后考虑你进行这一步操作之后会对你下一个状态造成什么影响
然后再加上之前状态表示中你决策出来的那个DP属性
这样就可以自然而然地搞出来转移方程啦
1)删除操作:把a[i]删掉之后a[1i]和b[1j]匹配
所以之前要先做到a[1(i-1)]和b[1j]匹配
f[i-1][j] + 1
2)插入操作:插入之后a[i]与b[j]完全匹配,所以插入的就是b[j]
那填之前a[1i]和b[1(j-1)]匹配
f[i][j-1] + 1
3)替换操作:把a[i]改成b[j]之后想要a[1i]与b[1j]匹配
那么修改这一位之前,a[1(i-1)]应该与b[1(j-1)]匹配
f[i-1][j-1] + 1
但是如果本来a[i]与b[j]这一位上就相等,那么不用改,即
f[i-1][j-1] + 0
好的那么f[i][j]就由以上三个可能状态转移过来,取个min
作者:Shadow
链接:https://www.acwing.com/solution/AcWing/content/5607/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
需要注意初始化,就是比如a字符串n位,b0位,那么永远是需要n次操作。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
static int N = 1010, n, m;
static int f[][] = new int[N][N];
static char[] a, b;
public static void main(String[] args) throws IOException {
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
String aa = br.readLine();
a = aa.toCharArray();
s = br.readLine().split(" ");
m = Integer.parseInt(s[0]);
String bb = br.readLine();
b = bb.toCharArray();
for (int i = 0; i <= n; i++) f[i][0] = i;
for (int i = 0; i <= m; i++) f[0][i] = i;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (a[i - 1] == b[j - 1]) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
}
pw.println(f[n][m]);
pw.flush();
pw.close();
br.close();
}
}