Table of Contents
2.3 Dynamic programming algorithm implementation——conversion (editing, transformation) problem
2.3.1 String conversion problem
2.3.1.1Problems
2.3.1.2 Determine dynamic rules (DP, state transition equation) and initial value
(1) Insertion operation realizes state transfer
(2) Delete operation to achieve state transfer
(3) Replacement operation realizes state transfer
(4)Initial value
(5) Dynamic rules (DP, state transition equation)
2.3.1.3 Dynamic programming algorithm code implementation
(1)Complete code
(2) Program speed optimization
(3) Single row storage (rolling array storage)
2.3.2 Matrix transformation problem
2.3.2.1 Problem
2.3.2.2 Matrix multiplication
(1) Conditions for matrix multiplication
(2) Principle of matrix multiplication
(3) Matrix multiplication conforms to the associative law
(4) The number of multiplication operations (number of times) of multiplying two matrices
(5) Number of multiplication operations (number of times) for multiplication of multiple matrices under the associative law
(6) The number of rows and columns of the matrix obtained by multiplying multiple matrices
2.3.2.3 Determine dynamic rules (DP, state transition equation)
(1) Sub-state space and sub-state
(2) Dynamic rules (DP, state transition equation)
2.3.2.4 Determine the initial value
2.3.2.5 Factors of state transfer
2.3.2.6 Dynamic programming algorithm code implementation
2.3 Dynamic programming algorithm implementation——conversion (editing, transformation) problem
2.3.1 String conversion problem
2.3.1.1 problem
Edit Distance (Edit Distance), also called Levenshtein Distance (Levenshtein Distance), for two strings (or words), the minimum number of operations required to convert one string into another string.
2.3.1.2 Determine dynamic rules (DP, state transition equation), initial value
Remember A=’kitten’, B=’sitting’, find the minimum number of operations required to convert string A into string B. There are three operations to convert a string into another string: insertion, deletion, and substitution.
For computers to convert A to B, it is more suitable to rely on a loop to gradually convert the characters in A into characters that successfully match B. In this process, insertion, deletion or replacement operations are used to achieve this, such as: ‘k’ in A Convert to ‘s’ in B, ‘k’ in A to ‘i’ in B,…, ‘i’ in A to ‘s’ in B, ‘i’ in A to ‘i’ in B,…, similar This is implemented one by one through loops. Obviously, this is different from people directly judging which positions need to be modified. If people modify it, just change the beginning and end. We can also let the computer do this kind of modification, but this method can only solve the problem. One situation cannot be generalized to other situations, and it is not suitable for the universal solution of the problem. Since computers are more suitable for this kind of step-by-step judgment, our algorithm must also conform to this computing characteristic, and the algorithm should be suitable for universality, so that such an algorithm can have generalization capabilities. We need to find a general rule that is suitable for computers to convert between all strings.
This operation is implemented by looping. Generally, insertion, deletion, and replacement operations are performed at the position where the index of the loop reaches, rather than performing these three operations at random positions. In computer loop judgment, converting one string into another string means changing the former by inserting, deleting or replacing. Finally, it will be the same length as the latter and the characters at the corresponding positions will be the same. The following analysis is actually described based on these characteristics of computers.
A[0:i] represents the local string composed of the first i characters of string A, and B[0:j] represents the local string composed of the first j characters of string B. During the calculation process, i and j take values along with the loop. We can remember that dp[i][j] is the minimum number of operations required to convert A[0:i] to B[0:j], i , j is obtained when A[0:i] and B[0:j] respectively represent their respective entire strings, which is the final state. This is also the problem we want. dp[i][j] can be regarded as the value of the ijth state. Since the ijth state below is unique, not multiple states, for the convenience of expression, the ijth state is also called the dp[i][j] state. Strictly speaking, the two should be distinguished, especially in some dynamic programming When the ijth state has multiple substates, they should be distinguished so that the concept is clearer.
In this example, insertion, deletion or replacement are ways to achieve state. These three ways determine that the current state dp[i][j] is composed of three directly related states dp[i][j-1], dp [i-1][j], dp[i-1][j-1] participate in the calculation.
The calculation of dp[i][j] is related to the directly related state. In this example, insertion, deletion or replacement are ways to achieve state. These three ways determine that the three states directly related to the current state dp[i][j] are dp[i][j-1], dp [i-1][j], dp[i-1][j-1]. Insertion corresponds to the operation on the dp[i][j-1] state, deletion corresponds to the operation on the dp[i-1][j] state, and replacement corresponds to the operation on the dp[i-1][j-1] state. operation.
Going from one state to another is accomplished by inserting, deleting, or replacing. dp[i][j] is related to the directly related state, and its generated directly related states are dp[i][j-1], dp[i-1][j], dp[i-1][j -1], and reaching a certain state is achieved by inserting, deleting or replacing. Here i and j represent the indexes of the original strings A and B. In the following analysis, the changes in index i and j are used to correspond to A. Insertion, deletion, or replacement are performed to gradually approach B. Note that in the following analysis, A is the original string unchanged. The insertion, deletion or replacement of A mentioned below tells us what we should do in this link. That is to say, the following analysis does not change the string A at the same time, and then Parse with the new changed string.
(1)Insert operation to achieve state transfer
The insertion operation implements state transfer, and the dp[i][j] state can only be transferred from dp[i][j-1]. From dp[i][j-1] to dp[i][j] state, i remains unchanged, while one character is added from j-1 to j, indicating that the length of A[0:i] remains unchanged during the state transition. , and the character shifting length of B[0:j] has increased by 1, so only insertion operations can be performed, so that their lengths may be consistent and the best situation occurs: inserting a character at the end of A[0:i] achieves dp[ The conversion with B[0:j] in i][j] state is successful. Therefore, the minimum number of operations from the dp[i][j-1] state to the dp[i][j] state is dp[i][j]=dp[i][j-1] + 1, and other deletions or replacements The number of operations will be greater than this number.
(2)Delete operation to achieve state transfer
The deletion operation implements state transfer, and the dp[i][j] state can only be transferred from dp[i-1][j]. From the dp[i-1][j] to the dp[i][j] state, i-1 becomes i, but j remains unchanged, indicating that the length of A[1:i] increases by 1 during the state transition. The character length of B[0:j] remains unchanged, so only deletion operations can be performed, so that their lengths may be consistent and the best situation occurs: deleting the last character of A[0:i] achieves dp[i][ j] state, the conversion with B[0:j] is successful. Therefore, the minimum number of operations from the dp[i-1][j] state to the dp[i][j] state is dp[i][j]=dp[i-1][j] + 1, other insertions or replacements The number of operations will be greater than this number.
(3)Replacement operation to achieve state transfer
The replacement operation implements state transfer, and the dp[i][j] state can only be transferred from dp[i-1][j-1]. From dp[i-1][j-1] to dp[i][j] state, i-1 becomes i, and j-1 becomes j. Both increase by 1, indicating that the state is transitioning. , the lengths of A[0:i] and B[0:j] have increased by 1 on the original basis, so they can only be replaced. Their lengths may be the same and the best situation occurs: replace the end of A[0:i] One character realizes the successful conversion with B[0:j] in the dp[i][j] state. When the character A[i] in A[0:i] and the character B[ in B[0:j] When j] is not the same, A[i] needs to be replaced by B[j], dp[i][j]= dp[i-1][j-1] + 1, but when A[i] and B[ When j] is the same, no replacement is needed. At this time, dp[i][j]= dp[i-1][j-1], and other insertion or deletion operations will be greater than this number.
dp[i][j] can be converted from one of the above three directly related states, so the minimum value min among the three directly related states can be taken, which is the minimum number of conversion operations we need. The above description is the dynamic rule DP under normal circumstances. Based on this DP, we can calculate the new state.
(4)Initial value
The initial state value is not necessarily calculated by the general state transition equation and can be artificially specified, but it should be consistent with the calculation of dynamic programming, so that the initial value can be obtained during computer calculation and consistent with the solution of the problem.
The source of the initial state is the conversion of null characters into non-null characters. If A is a null character and B is not a null character, A is converted to B[0:j], and 0 is used to represent the index of the null character, which also represents the initial state. Obviously, dp[0][j]=j, which is equivalent to continuously inserting characters, j is the number of inserted characters; if A is a non-null character and B is a null character, A[0:i] is converted to B, obviously , dp[i][0]=i, which is equivalent to continuously deleting characters, i is the number of deleted characters. Of course, we can start the initial state from 1 character. Obviously, it is not as convenient to manually calculate from a null character. The initial value is generally calculated manually.
(5)Dynamic rules (DP, state transition equation)
The initial state in this example is a special case that needs to be handled separately. We can unify the initial value and the above general situation into the following dynamic rule DP (state transition equation):
Simplified to:
Among the simplified mathematical expressions above, equation ① can be regarded as a special case of the problem and is treated separately, while equation 2 can be regarded as a common case of the problem, that is, the dynamic rule DP (that is, the state equation).
In the two-level loop of the dynamic programming algorithm, the outer loop is i and the inner loop is j. i and j correspond to the indexes of the A and B strings. The relationship between states in the state equation can reflect the operational relationship. In a two-level loop, the outer loop runs i and the inner loop j traverses once.
Earlier we analyzed based on the fact that neither string A nor B is empty. The index of dp[i][j] is consistent with the index of the string. This does not affect the analysis, but now we add the null character just added. In the initial state, please note that the index of dp[i][j] becomes one more than the index of the string, as shown in Figure 2-10. Therefore, pay attention to the changes in the expression of i and j indexes in the code, otherwise, improper use may easily produce an exception prompt string index out of range.
Figure 2-10 Minimum number of operations for editing distance
The above analysis and the implementation of the following code can be understood in conjunction with Figure 2-10 below. The status of the red area is determined by the status of the surrounding blue, that is, converting ‘ki’ to ‘s’ requires at least 2 operations. In addition, A in the figure is the original string unchanged. The actual insertion, deletion or replacement of A tells us what should be done in this link. The following program code is to implement the editing problem.
2.3.1.3 Dynamic programming algorithm code implementation
(1)Full code
The following code is implemented according to the above analysis process, which fully reflects our discussion of dynamic programming above. The idea of dynamic programming algorithm can be seen from the code. We can combine the following code to understand the role of dynamic programming algorithm in this problem. application.
#Edit distance problem, the following A:str indicates that A is a string, indicating the effect of the data type, the following can be written as (A, B)
def edit_distance(A:str, B:str):
#Increase 1 because the initial value adds rows and columns related to null characters.
n, m = len(A) + 1, len(B) + 1
#Initialization, generate a two-level list to store status values.
dp= [[0] * m for i in range(n)]
#Initial value, the initial value in this example actually corresponds to a special situation.
#dp[0][0] = 0#The value has been assigned when defining the list.
for i in range(1, n):#Handling of null characters
dp[i][0] = i #That is, dp[i][0]=dp[i - 1][0] + 1
for j in range(1, m):#Handling of null characters
dp[0][j] = j# that is, dp[0][j]=dp[0][j - 1] + 1
#Normally, the i and j indexes here are the indexes of dp, and 0 represents a null character, so the index starts from 1.
for i in range(1, n):
for j in range(1,m):
#Below, please pay attention to the index values of A and B. Their indexes are not the index values corresponding to dp. You need to subtract 1 to make them correspond exactly.
#Because dp adds rows and columns for null character processing, dp has one more row and column.
#So A[i - 1], B[j - 1] just correspond to the current state dp[i][j].
if A[i - 1] == B[j - 1]:
temp = 0
else:
temp=1
dp[i][j] = min(dp[i-1][j] + 1,dp[i][j-1] + 1,dp[i-1][j-1] + temp)#dynamic Rules(DP)
# dp output line by line
for i in range(n):
print(dp[i])
return dp[- 1][- 1]
A='kitten'
B