[Golang Theme Learning month] Over the weekend, I have done several dynamic programming questions and released a super exquisite teaching version, which has a very good response. Next, I will use two languages to brush the coding questions, respectively GO and JAVA.

πŸ˜„ Today this question is very practical, this algorithm is widely used by data scientists, is used as a basic algorithm for machine translation and speech recognition evaluation standards, of course, it is not difficult, come on to master it!


If you are not familiar with dynamic programming, please refer to this chapter \color{red}{if you are not familiar with dynamic programming, please refer to this chapter ~}

Liver for many days – dynamic planning ten even – super delicate analysis | brush title punch card

What problem can I choose to do dynamic programming?

Counting 1.

  • How many ways can I get to the bottom right corner
  • How many ways can I pick the sum of k numbers yes is sum

2. Find the maximum and minimum

  • The maximum numeric sum of the path from the upper left corner to the lower right corner
  • Maximum ascending subsequence length

3. Seek existence

  • Stone game, whether the first hand will win
  • Can we pick k numbers such that the sum is sum

Leecode 72. Edit distance

Given two words word1 and word2, please calculate the minimum operand needed to convert word1 into word2.

You can do one of three things with a word:

Insert a character delete a character replace a character

Example 1:

Enter: word1 = “horse”, word2 = “ros”

Output: 3

Explanation:

Horse -> rorse (replace ‘h’ with ‘r’)

Rorse -> rose (delete ‘r’)

Rose -> ros (delete ‘e’)

Example 2:

Input: word1 = “intention”, word2 = “execution”

Output: 5

Explanation:

Intention -> inention (delete ‘t’)

Inention -> enention (replace ‘I’ with ‘e’)

Enention -> exention (replace ‘n’ with ‘x’)

Exention -> exection (replace ‘n’ with ‘c’)

Exection -> execution (insert ‘u’)

Tip:

0 <= word1. Length, word2.length <= 500 Word1 and word2 are lowercase letters

—

In fact, this problem is similar to the minimum coin combination idea, each traversal has three choices (link to the second question above).

We can use word1 to iterate over word2, which will reduce the complexity. Then how do you represent the three choices ❀️❀️❀️❀️

2.1. Dynamic planning component 1: State determination

To put it simply, when solving dynamic programming, you need to open an array. What does each element of the array f[I] or f[I][j] represent, similar to what x, y, and z represent in mathematical problems

The last step

This is a general maximization problem, considering dynamic programming, storing computed values.

For example, if word1=”AB”,word2=”B”, deleting A for word1 is exactly the same as inserting A for word2. Therefore, we can convert these three operations:

Word1 insert, word2 insert, word1word2 modify each other

In traversal, each letter of word2 needs to be traversed by each letter of word1

Word1 = horse word2 = ros

The last step is simply the letter E matching the letter S for word2

subproblems

It says the last step is to match the letter e to the letter s for word2

If the last step requires word1 insertion: we can derive f[I][j-1] + 1, because we already know the minimum number of conversions (already in the array when iterated) for word2 0 in word1, plus the last insertion.

If the last step requires word2 insertion: we can derive f[i-1][j] + 1, because we already know the minimum number of conversions for word2 s in word1, plus the last insertion.

If the last step requires modification of word1word2 to each other: we can derive f[i-1][j-1] + 1, because we already know the minimum conversion number of word1 s to word2 0, plus the last modification.

If the last step itself is equal: then f[i-1][j-1] requires only the minimum number of conversions of the previous step.

So the minimum number of conversions:

The last letter is the same: min {f [I – 1) [j] + 1, f [I]] [j – 1 + 1, f [1] [I – 1]}

The last letter is not the same: min {f [I – 1) [j] + 1, f [I]] [j – 1 + 1, f [1] [I – 1] + 1}


Is not feeling suddenly suddenly open to the world πŸ†πŸ†πŸ†πŸ†πŸ† \color{red}{πŸ†πŸ†πŸ†πŸ†πŸ†~}

2.2. Dynamic programming component 2: Transfer equation

Set state f[I][j] to the minimum number of transitions between word1 and word2

For any I and j

Last letter is the same: [I] [j] f = min {f [I – 1) [j] + 1, f [I]] [j – 1 + 1, f [I – 1] [1]}

Last letter is not the same: [I] [j] f = min {f [I – 1) [j] + 1, f [I]] [j – 1 + 1, f] [I – 1 + 1} [1]

2.3. Dynamic programming component 3: Initial conditions and boundary cases

Initial conditions: If word1 is null, then the length of word2 needs to be converted from word1 to word2. Similarly, if word2 is null, then the length of word1 needs to be converted from word2

Int [][] D = new int[n + 1][m + 1];

2.4. Dynamic programming component 4: Order of calculation

Word1 iterates over each letter of Word2 in turn

Reference code

The language version

func minDistance(word1 string, word2 string) int {
        n1, n2 := len(word1), len(word2)

        dp := make([] []int, n1+1)
        for i := range dp {
            dp[i] = make([]int, n2+1)}for i := 0; i <= n1; i++ {
            dp[i][0] = i
        }
        for i := 0; i <= n2; i++ {
            dp[0][i] = i
        }
        w1, w2, f := 0.0.0
        for i := 1; i <= n1; i++ {
            for j := 1; j <= n2; j++ {
                w2 = dp[i- 1][j]+1 / / insert word2
                w1 = dp[i][j- 1] +1  / / word1 inserted
                f = dp[i- 1][j- 1]   / / modify
                if word1[i- 1] != word2[j- 1] {
                    f = dp[i- 1][j- 1] + 1  // 不同+1
                }
                dp[i][j] = Min(
                        w1,
                        w2,
                        f)
                
            }
        }

        return dp[n1][n2]
    }

    func Min(args ...int) int {
        min := args[0]
        for _, item := range args {
            if item < min {
                min = item
            }
        }
        return min
    }

Copy the code

JAVA version

 public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        // There is an empty string
        if (n * m == 0) {
            return n + m;
        }

        / / DP array
        int[][] D = new int[n + 1][m + 1];

        // The boundary state is initialized
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }

        // Calculate all DP values
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int word2Insert = D[i - 1][j] + 1; / / insert word2
                int word1Insert = D[i][j - 1] + 1;  / / word1 inserted
                int left_down = D[i - 1][j - 1]; // Same change
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    left_down += 1; // 不同+1} D[i][j] = Math.min(word1Insert, Math.min(word2Insert, left_down)); }}return D[n][m];
    }
    @Test
    public void isminDistance(a) {
        int i = minDistance("horse"."ros");
        Assert.assertNotNull(i);
    }

Copy the code

❀ ️ ❀ ️ ❀ ️ ❀ ️

Thank you very much talent can see here, if this article is written well, feel that there is something to ask for praise πŸ‘ for attention ❀️ for share πŸ‘₯ for handsome Oba I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much!

At the end of this article, I recently compiled an interview material “Java Interview Process Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, databases, data structures and so on. How to obtain: GitHub github.com/Tingyu-Note… , more attention to the public number: Ting rain notes, one after another.