間違って入力された字幕の文字列 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.長さ]);