AcWing 902. Minimum edit distance
Given the two strings A and B, now you want to change A into B through several operations. The available operations are:
 Delete – deletes A character from string A.
 Insert – inserts A character somewhere in string A.
 Replace – replaces one character in string A with another.
Now please find out how many operations it takes to change A to B at least.
Input format
The first line contains the integer n, which represents the length of string A.
The second line contains A string A of length n.
The third line contains the integer m, which represents the length of string B.
The fourth line contains a string B of length m.
Strings contain only uppercase letters.
Output format
Outputs an integer representing the minimum number of operations.
Data range
1≤n,m≤1000
Input example:
10
AGTCTGACGC
11
AGTAAGTAGGC
Output example:
4
Problem solution
Status representation dp[i][j]
 Set: the set of operations that turns a[1~i] into a set of b[1~j]
 Property: the operand of the scheme with the least number of operations among all operations
State calculation
The state is divided into different operations on the ith letter in a

Add after the letter
After adding a letter, it becomes the same, indicating that the first i of a and the first j1 of b are the same
Namely: dp[i][j] = dp[i][j1] + 1 
Delete the letter
After deleting the letter, it becomes the same, indicating that the first i1 in a has been the same as the first j in b
Namely: dp[i][j] = dp[i1][j] + 1 
Replace the letter
 If the corresponding ending letter of the replacement description is different, see the penultimate one
Namely: dp[i][j] = dp[i1][j1] + 1
Do nothing  The corresponding ending letter is the same, and the penultimate one is directly compared
Namely: dp[i][j] = dp[i1][j1]
 If the corresponding ending letter of the replacement description is different, see the penultimate one
n = int(input()) s1 = input() s1 = " " + s1 m = int(input()) s2 = input() s2 = " " + s2 dp = [[1e18] * (m + 1) for i in range(n + 1)] # Boundary condition # Only delete for i in range(1, n + 1): dp[i][0] = i # Only add for j in range(1, m + 1): dp[0][j] = j dp[0][0] = 0 for i in range(1, n + 1): for j in range(1, m + 1): # change if s1[i] == s2[j]: dp[i][j] = min(dp[i][j], dp[i  1][j  1]) else: dp[i][j] = min(dp[i][j], dp[i  1][j  1] + 1) # Delete dp[i][j] = min(dp[i][j], dp[i  1][j] + 1) # plus dp[i][j] = min(dp[i][j], dp[i][j  1] + 1) print(dp[1][1])
2553. Optimal inclusion
We call a string s containing string T, which means that T is a subsequence of S, that is, several characters can be extracted from string s, which are combined into a new string in the original order, which is exactly the same as T.
Given two strings S and T, how many characters in s can be modified at least to make s contain t?
Input format
Enter two lines, one string per line.
The string in the first line is S and the string in the second line is T.
Both strings are non empty and contain only uppercase letters.
Output format
Output an integer representing the answer.
Data range
1≤T≤S≤1000
Input example:
ABCDEABCD
XAABZ
Output example:
3
Problem solution
Status representation dp[i][j]
 Set: the set of operations that turns a[1~i] into a set of b[1~j]
 Property: the operand of the scheme with the least number of operations among all operations
State calculation
The state is divided into different operations on the ith letter in a
 unchanged
Different from the above question, this is a sub sequence.
dp[i][j] = dp[i  1][j]  Replace the letter
 If the corresponding ending letter of the replacement description is different, see the penultimate one
Namely: dp[i][j] = dp[i1][j1] + 1
Do nothing  The corresponding ending letter is the same, and the penultimate one is directly compared
Namely: dp[i][j] = dp[i1][j1]
 If the corresponding ending letter of the replacement description is different, see the penultimate one
s1 = input() s2 = input() n = len(s1) m = len(s2) s1 = " " + s1 s2 = " " + s2 dp = [[1e18] * (m + 1) for i in range(n + 1)] for i in range(0, n + 1): dp[i][0] = 0 for i in range(1, n + 1): for j in range(1, m + 1): dp[i][j] = min(dp[i][j], dp[i  1][j]) if s1[i] == s2[j]: dp[i][j] = min(dp[i][j], dp[i1][j1]) else: dp[i][j] = min(dp[i][j], dp[i  1][j  1] + 1) print(dp[1][1])