Java Dynamic Programming editing distance problem example code

The dynamic programming process is: each decision depends on the current state, and then causes the state transition. A decision sequence is produced in the changing state. Therefore, this multi-stage optimal decision-making process is called dynamic programming.

Dynamic programming is actually a general term for a class of problems, not a fixed algorithm. The significance of dynamic programming is through the use of recursion (or divide and conquer) strategy, which solves the whole problem by solving the sub problems of large problems. The core idea of dynamic programming is to skillfully divide the problem into multiple sub problems and obtain the solution of the whole problem by calculating the sub problems. The sub problems can be divided into more sub problems, so as to solve the required problem by a method similar to recursive iteration. Problem Description:

For sequences s and T, the distance between them is defined as: perform the following operations on one of them: 1, delete a character; 2. Insert a character; 3. Change one character For each operation, the count increases by 1 The minimum count of sequences that make s and t equal is their edit distance, or similarity Please give the corresponding algorithm and its implementation

analysis:

Suppose that the lengths of sequences s and T are m and N respectively, and the editing distance between them is expressed as edit [M] [n] The following situations exist when operating the sequence:

a. When the end characters of S and T are equal, there is no need to perform any of the above definition operations (i.e. "Edit") on the end characters, that is, there is no need to increase the count Then the condition is met: edit [M] [n] = edit [M-1] [n-1]

b. When the end characters of S and T are not equal, you need to edit the end of one of them, and the corresponding count will increase by 1

B1, modify the end of s or T to make it equal to t or s, then edit [M] [n] = edit [M-1] [n-1] + 1;

B2, delete the element at the end of s to make s equal to t, then edit [M] [n] = edit [M-1] [n] + 1;

B3, delete the element at the end of t to make t equal to s, then edit [M] [n] = edit [M] [n-1] + 1;

B4. Add the tail element of t at the end of s to make s and t equal, and then the length of s becomes m + 1. However, at this time, the tail elements of S and T are equal. Only the first m elements of S and the first n-1 elements of t need to be compared, so edit [M] [n] = edit [M] [n-1] + 1 is satisfied;

B5, add the tail element of s at the end of t to make t and s equal. At this time, the situation is the same as B4, which satisfies edit [M] [n] = edit [M-1] [n] + 1;

c. In a special case, when s is empty, edit [0] [n] = n; When t is empty, edit [M] [0] = m; This is well understood. For example, for sequences "" and "ABC", the minimum operation of both is 3, that is, sequence "" is inserted 3 times, or sequence "ABC" is deleted 3 times

Therefore, it is not difficult for us to deduce the dynamic programming equation of editing distance as follows:

Therefore, the recursive implementation of the dynamic programming algorithm for string editing distance can be represented by the following java code:

UPDATE:

At the same time, from the dynamic programming equation of editing distance, we can see that edit [M] [n] can be obtained by edit [M - 1] [n - 1], edit [M - 1] [n], edit [M] [n - 1], and if edit is a two-dimensional array, edit [M] [n] can be obtained by conditional judgment from its upper, left and upper left elements That is, we can calculate the current value by traversing the two-dimensional array and then backtracking

For example, for strings S = "sailn" and T = "failing", initialize the two-dimensional array as:

Because s [0] = s, t [0] = f, then s [0]= T [0], then corresponding to the above two-dimensional matrix, edit [1] [1] = min (edit [0] [0], edit [0] [1], edit [1] [0]) + 1, that is, edit [1] [1] = min (0,1,1) + 1, that is, edit [1] [1] = 0 + 1 = 1

For s [1] = a, t [1] = a, s [1] = t [1], it corresponds to a two-dimensional matrix, edit [2] [2] = edit [1] [1], so edit [2] [2] = 1 Therefore, according to this rule, filling the above two-dimensional matrix is as follows:

Therefore, the editing distance between the two is edit [M] [n] = edit [5] [7] = 3

Therefore, according to the above idea, the Java version of the backtracking solution of dynamic programming can be carried out as follows:

summary

The above is the whole content of the sample code on the editing distance of Java Dynamic Programming in this paper. I hope it will be helpful to you. Interested friends can continue to refer to other related topics on this site. If there are deficiencies, please leave a message to point out.