要把输错的字幕字符串 A 改成正确的字符串 B。
修改操作有三种，每做一次都要付出费用。
插入：在任意位置插入一个字符。
费用是 I。
删除：删掉一个字符。
费用是 D。
替换：把一个字符换成另一个字符。
费用是 R。
按任意顺序做任意多次这三种操作，让 A 与 B 完全相同，输出费用总和的最小值。
如果 A 和 B 一开始就相同，输出 0。
1 1 5 abcd abxd
2
3 2 4 banana bandana
3
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
这是用表 dp[i][j] ="把 A 的前 i 个字符变成 B 的前 j 个字符的最小费用"来解的动态规划。
看最后一个字符只有三条路：相同就保留（dp[i-1][j-1]），不同就替换（dp[i-1][j-1] + R），删除 A 的第 i 个字符（dp[i-1][j] + D），插入 B 的第 j 个字符（dp[i][j-1] + I），取其中最小的。
像第一个例子那样 R 很大时，不替换而是删除再插入（1 + 1 = 2）更便宜——因为取最小值，会自动处理。
一个格子只看上一行和当前行，所以只带着两行就够了（用两个 1,001 格的行代替 1,001 × 1,001 的表）。
陷阱一：把插入和删除写反，在 I ≠ D 时会错——写出 B 中的字符（j 减一的那边）才是插入。
陷阱二：第一行和第一列不是字符数，而是 j * I（向空字符串全部插入）和 i * D（全部删除）——只想着费用为 1 的普通编辑距离写成 j、i 就错了。
陷阱三：只在一行上覆盖写，row[j-1] 已经是本行的值，左上（对角）的值就丢了——要用两行，或者另外保存对角值。
交换两行的方法各语言不同：C 交换两个指针，C++ 的 std::swap(prev, cur) 只交换向量内部、没有复制，Java 交换数组引用，C# 用元组 (prev, cur) = (cur, prev)。
Python、JavaScript、TypeScript、Craykon 每行新建一个列表，用 prev = cur 接过来（Craykon 新列表(b.长度 + 1, 0)）。
读字符的方法也不同：Python、JavaScript、TypeScript、C# 用 a[i - 1]，Java 用 a.charAt(i - 1)，C 像 scanf("%1001s", a) 这样限定宽度读入数组，Craykon 用 控制台.读行().去空白() 读到的字符串中 a[i - 1] 是单个字符的字符串，用 == 比较。
费用最多 1,000 × 1,000 × 2 = 200 万，所以各语言用 int 都够。
import sys lines = sys.stdin.read().split()ins, dele, rep = int(lines[0]), int(lines[1]), int(lines[2])a, b = lines[3], lines[4] # prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(한 줄만 들고 간다)prev = [j * ins for j in range(len(b) + 1)] # 빈 문자열에서 b의 앞 j글자: 모두 넣기for i in range(1, len(a) + 1): cur = [i * dele] + [0] * len(b) # a의 앞 i글자에서 빈 문자열: 모두 빼기 for j in range(1, len(b) + 1): keep = prev[j - 1] + (0 if a[i - 1] == b[j - 1] else rep) # 그대로 두거나 바꾸기 cur[j] = min(keep, prev[j] + dele, cur[j - 1] + ins) # a[i-1] 빼기, b[j-1] 넣기 prev = cur print(prev[len(b)])const [ins, del, rep, a, b] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const I = Number(ins), D = Number(del), R = Number(rep); // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(한 줄만 들고 간다)let prev = Array.from({ length: b.length + 1 }, (_, j) => j * I); // 빈 문자열에서: 모두 넣기for (let i = 1; i <= a.length; i++) { const cur = new Array(b.length + 1); cur[0] = i * D; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (let j = 1; j <= b.length; j++) { const keep = prev[j - 1] + (a[i - 1] === b[j - 1] ? 0 : R); // 그대로 두거나 바꾸기 cur[j] = Math.min(keep, prev[j] + D, cur[j - 1] + I); // a[i-1] 빼기, b[j-1] 넣기 } prev = cur;}console.log(prev[b.length]);import { readFileSync } from "node:fs"; const [ins, del, rep, a, b] = readFileSync(0, "utf8").trim().split(/\s+/);const I = Number(ins), D = Number(del), R = Number(rep); // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(한 줄만 들고 간다)let prev: number[] = Array.from({ length: b.length + 1 }, (_, j) => j * I); // 빈 문자열에서: 모두 넣기for (let i = 1; i <= a.length; i++) { const cur: number[] = new Array<number>(b.length + 1); cur[0] = i * D; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (let j = 1; j <= b.length; j++) { const keep = prev[j - 1] + (a[i - 1] === b[j - 1] ? 0 : R); // 그대로 두거나 바꾸기 cur[j] = Math.min(keep, prev[j] + D, cur[j - 1] + I); // a[i-1] 빼기, b[j-1] 넣기 } prev = cur;}console.log(prev[b.length]);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int ins = Integer.parseInt(st.nextToken()); int del = Integer.parseInt(st.nextToken()); int rep = Integer.parseInt(st.nextToken()); String a = in.readLine().trim(); String b = in.readLine().trim(); // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(두 줄만 번갈아 쓴다) int[] prev = new int[b.length() + 1]; int[] cur = new int[b.length() + 1]; for (int j = 0; j <= b.length(); j++) prev[j] = j * ins; // 빈 문자열에서: 모두 넣기 for (int i = 1; i <= a.length(); i++) { cur[0] = i * del; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (int j = 1; j <= b.length(); j++) { int keep = prev[j - 1] + (a.charAt(i - 1) == b.charAt(j - 1) ? 0 : rep); // 그대로 두거나 바꾸기 cur[j] = Math.min(keep, Math.min(prev[j] + del, cur[j - 1] + ins)); // 빼기, 넣기 } int[] t = prev; // 두 줄을 맞바꾼다(새로 만들지 않는다) prev = cur; cur = t; } System.out.println(prev[b.length()]); }}using System; class Program{ static void Main() { string[] c = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int ins = int.Parse(c[0]), del = int.Parse(c[1]), rep = int.Parse(c[2]); string a = Console.ReadLine().Trim(); string b = Console.ReadLine().Trim(); // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(두 줄만 번갈아 쓴다) var prev = new int[b.Length + 1]; var cur = new int[b.Length + 1]; for (int j = 0; j <= b.Length; j++) prev[j] = j * ins; // 빈 문자열에서: 모두 넣기 for (int i = 1; i <= a.Length; i++) { cur[0] = i * del; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (int j = 1; j <= b.Length; j++) { int keep = prev[j - 1] + (a[i - 1] == b[j - 1] ? 0 : rep); // 그대로 두거나 바꾸기 cur[j] = Math.Min(keep, Math.Min(prev[j] + del, cur[j - 1] + ins)); // 빼기, 넣기 } (prev, cur) = (cur, prev); // 두 줄을 맞바꾼다(새로 만들지 않는다) } Console.WriteLine(prev[b.Length]); }}#include <algorithm>#include <iostream>#include <string>#include <vector> int main() { int ins, del, rep; std::string a, b; std::cin >> ins >> del >> rep >> a >> b; // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(두 줄만 번갈아 쓴다) std::vector<int> prev(b.size() + 1), cur(b.size() + 1); for (size_t j = 0; j <= b.size(); j++) prev[j] = static_cast<int>(j) * ins; // 빈 문자열에서: 모두 넣기 for (size_t i = 1; i <= a.size(); i++) { cur[0] = static_cast<int>(i) * del; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (size_t j = 1; j <= b.size(); j++) { int keep = prev[j - 1] + (a[i - 1] == b[j - 1] ? 0 : rep); // 그대로 두거나 바꾸기 cur[j] = std::min({keep, prev[j] + del, cur[j - 1] + ins}); // 빼기, 넣기 } std::swap(prev, cur); // 벡터 속만 맞바꾼다(복사하지 않는다) } std::cout << prev[b.size()] << "\n";}#include <stdio.h>#include <string.h> #define MAXL 1000 static char a[MAXL + 2], b[MAXL + 2];static int row0[MAXL + 1], row1[MAXL + 1]; static int min3(int x, int y, int z) { int m = x < y ? x : y; return m < z ? m : z;} int main(void) { int ins, del, rep; scanf("%d %d %d", &ins, &del, &rep); scanf("%1001s %1001s", a, b); int n = (int)strlen(a), m = (int)strlen(b); /* prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(두 줄만 번갈아 쓴다) */ int* prev = row0; int* cur = row1; for (int j = 0; j <= m; j++) prev[j] = j * ins; /* 빈 문자열에서: 모두 넣기 */ for (int i = 1; i <= n; i++) { cur[0] = i * del; /* a의 앞 i글자에서 빈 문자열: 모두 빼기 */ for (int j = 1; j <= m; j++) { int keep = prev[j - 1] + (a[i - 1] == b[j - 1] ? 0 : rep); /* 그대로 두거나 바꾸기 */ cur[j] = min3(keep, prev[j] + del, cur[j - 1] + ins); /* 빼기, 넣기 */ } int* t = prev; /* 포인터만 맞바꾼다 */ prev = cur; cur = t; } printf("%d\n", prev[m]); return 0;}비용 = 控制台.读数字();ins = 비용[0];del = 비용[1];rep = 비용[2];a = 控制台.读行().去空白();b = 控制台.读行().去空白(); // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(한 줄만 들고 간다)prev = [];循环 (j = 0; j <= b.长度; j++){ prev.添加(j * ins); // 빈 문자열에서 b의 앞 j글자: 모두 넣기}循环 (i = 1; i <= a.长度; i++){ cur = 新列表(b.长度 + 1, 0); cur[0] = i * del; // a의 앞 i글자에서 빈 문자열: 모두 빼기 循环 (j = 1; j <= b.长度; j++) { keep = prev[j - 1] + rep; // 다른 글자로 바꾸기 如果 (a[i - 1] == b[j - 1]) { keep = prev[j - 1]; // 같은 글자는 그대로 둔다 } cur[j] = 数学.较小值(keep, 数学.较小值(prev[j] + del, cur[j - 1] + ins)); // 빼기, 넣기 } prev = cur;}控制台.输出(prev[b.长度]);