Khoảng cách biến đổi xâu

Buổi 22 — DP 2D & LIS Dynamic Programming Strings
Points
16
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho hai xâu ký tự $S$ và $T$. Trong một phép biến đổi trên xâu $S$, bạn có thể thực hiện một trong ba thao tác:

  1. Chèn một ký tự vào vị trí bất kỳ.
  2. Xóa một ký tự.
  3. Thay thế một ký tự bằng một ký tự khác.

Hãy tìm số phép biến đổi ít nhất để biến xâu $S$ thành xâu $T$.

Cấu trúc con tối ưu: $dp[i][j]$ là số phép biến đổi ít nhất để biến $i$ ký tự đầu của $S$ thành $j$ ký tự đầu của $T$.

Dữ liệu vào

Dòng đầu tiên chứa xâu $S$. Dòng thứ hai chứa xâu $T$.

Dữ liệu ra

Một số nguyên duy nhất là khoảng cách biến đổi nhỏ nhất.

Ví dụ
Input Output
horse
ros
3
intention
execution
5
Giới hạn

$1 \le |S|, |T| \le 1000$, các xâu chỉ gồm chữ cái in thường.

Draft saved