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]

1. Set: the set of operations that turns a[1~i] into a set of b[1~j]
2. 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

1. Add after the letter
   After adding a letter, it becomes the same, indicating that the first i of a and the first j-1 of b are the same
   Namely: dp[i][j] = dp[i][j-1] + 1

2. Delete the letter
   After deleting the letter, it becomes the same, indicating that the first i-1 in a has been the same as the first j in b
   Namely: dp[i][j] = dp[i-1][j] + 1

3. Replace the letter

   • If the corresponding ending letter of the replacement description is different, see the penultimate one
     Namely: dp[i][j] = dp[i-1][j-1] + 1
     Do nothing
   • The corresponding ending letter is the same, and the penultimate one is directly compared
     Namely: dp[i][j] = dp[i-1][j-1]

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]

1. Set: the set of operations that turns a[1~i] into a set of b[1~j]
2. 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

1. unchanged
   Different from the above question, this is a sub sequence.
   dp[i][j] = dp[i - 1][j]
2. Replace the letter
   • If the corresponding ending letter of the replacement description is different, see the penultimate one
     Namely: dp[i][j] = dp[i-1][j-1] + 1
     Do nothing
   • The corresponding ending letter is the same, and the penultimate one is directly compared
     Namely: dp[i][j] = dp[i-1][j-1]

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[i-1][j-1])
        else:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
print(dp[-1][-1])