The depth is very deep, and you don’t know if you can’t come out

Thesis: two dimensional dynamic programming algorithm

Given two strings text1 and text2, return the length of the longest common subsequence of the two strings. If no common subsequence exists, return 0.

A subsequence of a string is a new string made up of the original string without changing the relative order of the characters by deleting some characters (or none).

For example, “ace” is a subsequence of “ABCDE”, but “AEC” is not a subsequence of “ABCDE”.

A common subsequence of two strings is a subsequence that is shared by both strings.

Example 1: Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace", which has length 3. Example 2: Input: text1 = "ABC ", text2 =" ABC "Output: 3 Explanation: The longest common subsequence is" ABC ", which has length 3. Example 3: Input: text1 = "ABC ", text2 = "def" Output: 0 Explanation: The two strings have no common subsequence, return 0.Copy the code

Finding the longest common subsequence is complicated. The key point is that the subsequence does not need to be continuous. Non-continuous characters can also form subsequences. If the common substring, then the use of violence enumeration is very easy to solve, but if the subsequence permutation of the situation is too much, it is not suitable for the use of violence enumeration method.

Any situation where the next execution state is judged according to the state of the previous step, dynamic programming is generally given priority to solve the problem. However, how to realize the dynamic programming of two arrays involves the derivation of dynamic programming: two-dimensional dynamic programming.

First of all, let’s take a look at the analysis of the official two-dimensional dynamic programming:

It’s hard to understand if, well, we can parse around a scheme like this, and then look at the two-dimensional dynamic programming problem.

First of all, the beginning

Given that the strings text1 and text2 are of length m,n, create a two-dimensional array with m+1 rows and n+1 columns

It makes sense to create a two-dimensional array in order to loop inside and out to find each case, but why a spatial array with rows M + 1 and n + 1? I can put that aside for the moment, because if I think about it first, I’m going to create an array of m and n columns, and maybe I’ll run into some problems later, and I’ll realize that m plus 1 and N plus 1 columns are actually more appropriate. Until we encounter this problem, we default to m rows and n columns.

Then a matrix dpList[] can be obtained:

Row and column subscripts are I and j, respectively. DpList [I][j] is used to represent the largest possible common subsequence of the ith character in Text1 and the JTH character in text 2. Let’s consider how to dynamically fill in these numbers.

When I = 0 and j = 0, text1 and text2 get only the first letter of the current string, a and B, respectively, and only two characters can form the largest common subsequence, either 1 or 0. Then 0 maximum common subsequences can be formed, so dpList[0][0] is filled with 0. As shown in figure:

When I = 0, j = 1, text1 the ith character a, text2 the JTH character D, a and D are not the same, that is, they cannot form a common subsequence fundamentally, so dpList[0][1] fill in 0, the first line and so on, When j = 2, dpList[0][2] is filled with 0.

When I = 0, j = 3, extract a and A, respectively, and the two characters are the same, then the largest common subsequence that text1 and text2 can form so far is A, with length 1

When I = 0, j = 4, take a and B, two different characters, do you fill in 0? Obviously not, because you are only considering the current a and B characters. The number we fill in takes into account the maximum length of the I and j nodes, that is, it must include the previous length. Maybe it’s a little hard to understand, but another way to think about it is when I = 0, j = 4 we’re not just thinking about whether a and B are public characters, Instead, it is the largest public string consisting of [a] and [b,d,c,a,b], that is, the longest public string consisting of all characters preceding a and B.

[a] and [b,d,c,a,b] have only one common string (a), and this was calculated in the previous step. If no new public string is formed after adding b, then the length of the previous step remains unchanged.

What is the length of the previous step? The answer is: the maximum value of the dpList for which I and j are -1. That is:

DpList [i-1][J-1], you need to consider the largest of the sequences of i-1 and j-1 as the maximum of the current most constant subsequence. If you find it difficult to understand, think of an example.

Therefore, the equations in the solution of the problem are obtained:

But as long as you have subtraction of I minus one and j minus one, there’s bound to be a boundary case, where I = 0 or j = 0, you can’t have subtraction of minus one. And to avoid that, you have the idea of having columns and columns plus one.

So that’s why I said in the beginning why I have a spatial array of m + 1 and n + 1 rows, because then dpList really computations can start at 1, and the outermost single character is not going to be a common subsequence so it’s all going to be 0, very neat.

The following is a supplementary procedure for the dynamic planning diagram:

And then you could do the same thing, and you would end up with a very similar dynamic plan.

Code implementation: Since we did not create columns and columns for m + 1 and n + 1, we need to consider the boundary case, where I and j are equal to 1, respectively.

var longestCommonSubsequence = function (text1, text2) {
  const l1 = text1.length
  const l2 = text2.length
  const dpList = []
  for (let index = 0; index < l1; index++) {
    dpList[index] = []
    for (let j = 0; j < l2; j++) {
      dpList[index].push(0)
    }
  }

  for (let i = 0; i < l1; i++) {
    for (let j = 0; j < l2; j++) {
      if (text1[i] === text2[j]) {
        dpList[i][j] = (i > 0 && j > 0) ? dpList[i - 1][j - 1] + 1 : 1
      } else {
        if (i > 0 && j > 0) {
          dpList[i][j] = Math.max(dpList[i - 1][j], dpList[i][j - 1])
        } else if (i > 0) {
          dpList[i][j] = dpList[i - 1][j]
        } else if (j > 0) {
          dpList[i][j] = dpList[i][j - 1]
        } else {
          dpList[i][j] = 0
        }
      }
    }
  }
  return dpList[l1 - 1][l2 - 1]
};
Copy the code

At this point, a case of two-dimensional dynamic programming is solved. To be honest, two-dimensional dynamic programming is abstract, and the state of each node is difficult to define, resulting in a relatively difficult to understand. In fact, the above said so much may not say to the point, but limited ability, expression ability is more limited. High war, please guide, like me, please feel! You have to do a lot of algorithmic problems like this to get to the bottom of it.

The algorithm problem similar to that solved by two-dimensional dynamic programming is recommended: solving the maximum square | matrix | minimum path sum

Learn more and practice more, be sure!