Dynamic programming is a common algorithm idea, many friends think it is not easy to understand, in fact, if you master his core ideas, and a lot of practice or can master. So let’s talk about dynamic programming from the bottom up.

Fibonacci sequence

First, let’s look at the Fibonacci sequence, which is a familiar sequence:

// f = [1, 1, 2, 3, 5, 8]
f(1) = 1;
f(2) = 1;
f(n) = f(n-1) + f(n -2); // n > 2

With the above formula, we can easily write the recursive code to compute f(n) :

function fibonacci_recursion(n) { if(n === 1 || n === 2) { return 1; } return fibonacci_recursion(n - 1) + fibonacci_recursion(n - 2); } const res = fibonacci_recursion(5); console.log(res); / / 5

Now, let’s think about the calculation above, so if we want to evaluate f(5), we want to evaluate f(3), we want to evaluate f(3), we want to evaluate f(3) twice. Given that we know f(1) and f(2), we only need to compute f(3), f(4), and f(5) three times, but we can see from the figure below that to compute f(5), we have to compute 8 other values in total, in which f(3), f(2), and f(1) are repeated many times. If n is not 5, but a larger number, and the number of computations increases exponentially, the time complexity of this recursive algorithm is $O(2 to the n)$.

Non-recursive Fibonacci sequences

In order to solve the exponential time complexity above, we can not use recursive algorithm, but a normal circular algorithm. How do you do that? All we need to do is add an array with the value of each item in it. To match the index of f(n), we fill the array with a 0 at the beginning:

const res = [0, 1, 1];
f(n) = res[n];

All we need to do is fill the res array with a value and return the NTH item:

function fibonacci_no_recursion(n) { const res = [0, 1, 1]; for(let i = 3; i <= n; i++){ res[i] = res[i-1] + res[i-2]; } return res[n]; } const num = fibonacci_no_recursion(5); console.log(num); / / 5

So we don’t have to double compute, because we’re storing it in an array every time, and we’re just using f(n-1) and f(n-2) to compute f(n), because we’re counting from small to large, so f(n-1) and f(n-2) before we do it. The time complexity of this algorithm is O(n), which is much better than $O(2^n)$. This algorithm actually uses the idea of dynamic programming.

Dynamic programming

Dynamic programming mainly has the following two characteristics

  1. Optimal substructure: a problem of size n can be transformed into a subproblem of size smaller than it to solve. In other words, f(n) can be solved by a smaller recursion than that, which is f(n) = f(n-1) + f(n-2) in the previous Fibonacci sequence. In general, problems with this structure can also be solved by recursion, but the complexity of recursion is too high.
  2. Overlapping of subproblems: If solving recursively, there will be many repeated subproblems. Dynamic programming is to trim the repeated calculations to reduce the time complexity. However, because of the need to store intermediate state, the space complexity is increased.

In fact, the difficulty of dynamic programming is to generalize the recursion, in the Fibonacci sequence, the recursion is already given, but more often we need to generalize the recursion by ourselves.

Steel bar cutting problem

Let’s start with a violent exhaustive example of a steel bar of length 5:

The red position in the figure above indicates the position where the cutting can be done. Each position can have two states of cutting and not cutting. In total, $2^4 = 16$kinds. Instead of writing code for the exhaustive method, let’s look at the recursive method:

Recursive scheme

Taking the steel bar of length 5 as an example, if we only consider the case of a cut, the position of the cut can be any position in 1,2,3,4, then after cutting, the length of the left and right sides are respectively:

// [left, right]: represents the length of the left and right sides [1, 4]: cut position 1 [2, 3]: cut position 3 [4, 1]: cut position 4

And then you can cut the left and the right again, and then you can cut the left and the right again, and then you can cut each of these again, and then you can cut the left and the left again. So we’re going to break a problem of length 5 into four small problems, and the best solution is the largest one of these four small problems, and remember we can do it without cutting at all, and this is the fifth small problem, and the answer we’re going to get is the largest of these five small problems. The formula is that, for steel bar of length n, the optimal return formula is:

  • $r_n$: denotes the goal of our solution, the maximum return of a steel bar of length n
  • $P_N $: Indicates that the steel bar is not cut at all
  • $r_1 + r_{n-1}$: indicates that it is cut at the position of 1 and divided into two ends of the length of 1 on the left and n-1 on the right. Their sum is the optimal return of this scheme
  • Our biggest benefit is to not cut and cut in different cases of the subscheme to find the maximum

The above formula can already be solved recursively:

const p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]; Function cut_rod(n) {if(n === 1) return 1; let max = p[n]; for(let i = 1; i < n; i++){ let sum = cut_rod(i) + cut_rod(n - i); if(sum > max) { max = sum; } } return max; } cut_rod(9); / / return to 25

The above formula can also be simplified, if our length 9 is the best solution to cut into 2, 3, 2, 2 in front of an algorithm, the first knife cut it into 2 7 and 4, 5, and then both sides separately can win 2 2, 2, 3, 5 4 so the final result and 2 7 solution is the same, will be 2, 3, 2, 2, So if you do both of these, and you keep cutting both sides, you’re actually going to double calculate. For the first cut of length 9, the value on the left must be 1 — 9, and we cut from 1, and if we continue to make cuts on the left, the value on the left must be one of the left values that we calculated before. So if you cut 5, 4 into 2, 3, 4, that’s the same thing as the first time you cut 2, 7, if you cut 3, 6 on the first time, if you keep cutting on the left, you cut 1, 2, 6, that’s the same thing as 1, 8, that’s what we did when we cut the left by 1. So if we cut the left side from 1 in turn, then we don’t have to cut the left side, we just cut the right side. Therefore, our formula can be simplified as:

$$ r_n = \max_{1<=i<=n}(pi+r_{n-i}) $$

Continue to implement this formula recursively:

const p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]; Function cut_rod2(n) {if(n === = 1) return 1; let max = p[n]; for(let i = 1; i <= n; i++){ let sum = p[i] + cut_rod2(n - i); if(sum > max) { max = sum; } } return max; } cut_rod2(9); // The result returns 25 again

The above two formulas are recursive, and the complexity is exponential. Now let’s talk about dynamic programming.

Dynamic programming scheme

The formula for dynamic programming is the same as the previous one, and we use the second simplified formula:

$$ r_n = \max_{1<=i<=n}(pi+r_{n-i}) $$

Dynamic programming is when you don’t recurse, you compute the values from the bottom up, and every time you compute the values from the top, you calculate the values from the bottom, and you just use them. So we need an array to record the maximum return for each length.

const p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]; Function cut_rod3(n) {let r = [0, 1]; // Array for(let I = 2; i <=n; i++) { let max = p[i]; for(let j = 1; j <= i; j++) { let sum = p[j] + r[i - j]; if(sum > max) { max = sum; } } r[i] = max; } console.log(r); return r[n]; } cut_rod3(9); // The result returns 25 again

We can also type out the r array, which contains the maximum return for each length:

r = [0, 1, 5, 8, 10, 13, 17, 18, 22, 25]

Using dynamic programming reduces the exponential complexity of the recursion to the complexity of the double loop, namely $O(n^2)$.

Output optimal scheme

Although the maximum value is calculated by the dynamic programming above, we do not know the cutting scheme corresponding to the maximum value. In order to know the scheme, we need an array to record the length of the left side when cutting once, and then backtrack in this array to find the cutting scheme. So when we go back, we take the left side of the target, and then the rest of the right side and we go back to the array and we look for the optimal cut to the left. Suppose our array of records on the left is:

leftLength = [0, 1, 2, 3, 2, 2, 6, 1, 2, 3]

We require the best cutting scheme for steel bars of length 9:

1. Find LeftLength [9], find the value of 3, and record 3 as one cut 2. After cutting 3 on the left, there was still 6 left on the right, and then went to look for LeftLength [6], and found that the value was 6, and recorded 6 as the length of one cut 3. After I cut another 6, I find that I still have 0 left, so I'm done, and I finish the cycle. If there are still steel bars left, continue to cut in this way. 4. The optimal length of output is [3, 6]

The transformation code is as follows:

const p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]; Function cut_rod3(n) {let r = [0, 1]; Let leftLength = [0, 1]; // array leftLength let solution = []; for(let i = 2; i <=n; i++) { let max = p[i]; leftLength[i] = i; Let j = 1; let j = 1; j <= i; j++) { let sum = p[j] + r[i - j]; if(sum > max) { max = sum; leftLength[i] = j; }} r[I] = Max;} r[I] = Max; } // let tempN = n; while(tempN > 0) { let left = leftLength[tempN]; solution.push(left); tempN = tempN - left; } console.log(leftLength); // [0, 1, 2, 3, 2, 2, 6, 1, 2, 3] console.log(solution); // [3, 6] console.log(r); // [0, 1, 5, 8, 10, 13, 17, 18, 22, 25] return {max: r[n], solution: solution}; } cut_rod3(9); // {max: 25, solution: [3, 6]}

The longest common subsequence (LCS)

If the length of the string is m, there will be a total of $2^m$situations. Since each character in the string has two states: keep and don’t leave, the total permutation of m characters is $2^m$. So the corresponding Y string would have $2 to the n$seed string, where n is the length of Y. And then I’m going to go through it and find the longest common subsequence, which is so complicated that I’m not going to write it here.

If we look at two strings, if their last character is the same, then their LCS is the LCS of both strings with the last character removed and one added. Because the last character is the same, so the last character is their subsequence, take it out, the subsequence is one less, so their LCS is the LCS of the string that they took out the last character plus one. If their last character is different, then the LCS of X minus the last character of Y, or the LCS of X minus the last character of Y, is the longer of the two. The mathematical formula is:

If you look at this formula, a problem of size (I, j) turns into a problem of size (I -1, j-1), then you can solve it recursively again.

Recursive scheme

I have the formula, no nonsense, just write the code:

function lcs(str1, str2) { let length1 = str1.length; let length2 = str2.length; if(length1 === 0 || length2 === 0) { return 0; } let shortStr1 = str1.slice(0, -1); let shortStr2 = str2.slice(0, -1); if(str1[length1 - 1] === str2[length2 - 1]){ return lcs(shortStr1, shortStr2) + 1; } else { let lcsShort2 = lcs(str1, shortStr2); let lcsShort1 = lcs(shortStr1, str2); return lcsShort1 > lcsShort2 ? lcsShort1 : lcsShort2; } } let result = lcs('ABBCBDE', 'DBBCD'); console.log(result); / / 4

Dynamic programming

Recursion can meet our needs, but the complexity is too high, and the time needed for longer strings grows exponentially. So again, we’re going to use dynamic programming, and based on the dynamic programming principles that we talked about, we’re going to have to go from small to large, and we’re going to write down every value that we get. Because C (I, j) has two variables in it, we need a two-dimensional array to store it. Notice that the number of rows in this two-dimensional array is the length of X plus one, and the number of columns is the length of Y plus one, because the first row and the first column represent the case where X or Y is an empty string. The code is as follows:

function lcs2(str1, str2) { let length1 = str1.length; let length2 = str2.length; Let result = []; // let result = []; // let result = []; for(let i = 0; i < length1 + 1; i++){ result.push([]); // For (let j = 0; j < length2 + 1; j++){ if(i === 0) { result[i][j] = 0; / / the first line of 0} all else if (j = = = 0) {result [I] [j] = 0; If (str1[j] == str2[j]){if(str1[j] == str2[j]){if(str1[j] == str2[j]); } else{result[I][j] = result[I][j - 1] > result[I - 1][j]? result[i][j - 1] : result[i - 1][j]; } } } console.log(result); return result[length1][length2] } let result = lcs2('ABCBDAB', 'BDCABA'); console.log(result); / / 4

If $X_i = Y_j$, then its value is the one above or to the left. If $X_i \neq Y_i$, then its value is the one above or to the left.

Outputs the longest common subsequence

To output the LCS, the idea is similar to the previous cutting of the steel bar. Write down each step of the operation and then go back. In order to record operations we need a two-dimensional array as large as the result two-dimensional array, with the values in each cell being where the current value came from. Of course, the first row and the first column are still 0. The value of each cell is either from above, above, or to the left, so:

2. We use 2 to indicate that the current value is coming from the left. 3. We use 3 for the current value coming from the top

Look at the code:

function lcs3(str1, str2) { let length1 = str1.length; let length2 = str2.length; Let result = []; // let result = []; // let result = []; let comeFrom = []; // save the array for(let I = 0; i < length1 + 1; i++){ result.push([]); // Comefro.push ([]); // Comefro.push ([]); for(let j = 0; j < length2 + 1; j++){ if(i === 0) { result[i][j] = 0; // ComeFrom [I][j] = 0; } else if(j === 0) { result[i][j] = 0; // ComeFrom [I][j] = 0; } else if (str1 = = = str2 [I - 1] [1]) {/ / the last one character at a same result [I] [j] = result [I - 1] [1] + 1; comeFrom[i][j] = 1; } else if(result[I][j] result[I][j] = result[I][j]){result[I][j] = result[j]; comeFrom[i][j] = 2; } else {// result[I][j] = result[I - 1][j]; comeFrom[i][j] = 3; } } } console.log(result); console.log(comeFrom); // backtrack ComeFrom array let Pointeri = length1; let pointerJ = length2; let lcsArr = []; While (pointerI > 0 && pointerJ > 0) {console.log(pointerI, pointerJ); if(comeFrom[pointerI][pointerJ] === 1) { lcsArr.push(str1[pointerI - 1]); pointerI--; pointerJ--; } else if(comeFrom[pointerI][pointerJ] === 2) { pointerI--; } else if(comeFrom[pointerI][pointerJ] === 3) { pointerJ--; } } console.log(lcsArr); / / / "B", "A", "D", "B"] / / lcsArr order now is an lcsArr = lcsArr. Reverse (); return { length: result[length1][length2], lcs: lcsArr.join('') } } let result = lcs3('ABCBDAB', 'BDCABA'); console.log(result); // {length: 4, lcs: "BDAB"}

Minimum Edit Distance

Here’s a question in LeetCode that describes it as follows:

Let’s also assume that the first string is $X=(X_1, X_2… $Y=(y_1, y_2… $Y=(y_1, y_2… Y_n) $. $r[I][j]$= $X$= $I $= $j$= $Y$= $j$= $I $= $X$= $j$= $Y$ We also start with the last character of the two strings:

  1. If $Xi = Y_j$, $r[I][j] = r[I -1][j-1]$, $I [j] = r[I -1][j-1]$, $I [j] = r[I -1][j-1]$, $I [j] = r[I -1][j-1]$, $I [j] = r[I -1][j-1]$
  2. If their last character is different, then the last character must be edited once. The minimum edit distance is $X $remove the last character with $Y $shortest edit distance, coupled with the last one character at a time; $X$= $Y$= $X$= $Y$= $X$; If $X$removes the last character, or if $Y$removes the last character, then $Y$inserts or deletes the last character. If $X$removes the last character, then $Y$removes the last character. If $X$removes the last character, then $Y$removes the last character. $r[I][j]=r[I -1][j-1]+1$. Is ultimately take the minimum value in the three conditions, written in mathematical formula is: if $Xi \ neq Y_j $, $r [j] = \ [I] min (r [j], [I – 1] r [1], [I] r [I – 1]] [j – 1) + 1 $.
  3. Finally, if either $X$or $Y$is an empty string, then to make them the same, insert another string into the empty string. The shortest distance is the length of the other string. If $I =0$, $r[I][j] = j$; $r[j] = j$; If $j=0$, $r[I][j] = I $.

All of the above can be summed up

$$ r[i][j]= \begin{cases} j, & \text{if}\ i=0 \\ i, & \text{if}\ j=0 \\ r[i-1][j-1], & \text{if}\ X_i=Y_j \\ \min(r[i-1][j], r[i][j-1], r[i-1][j-1]) + 1, & \text{if} \ X_i\neq Y_j \end{cases} $$

Recursive scheme

As usual, given the recursion formula, let’s write a recursion:

const minDistance = function(str1, str2) { const length1 = str1.length; const length2 = str2.length; if(! length1) { return length2; } if(! length2) { return length1; } const shortStr1 = str1.slice(0, -1); const shortStr2 = str2.slice(0, -1); const isLastEqual = str1[length1-1] === str2[length2-1]; if(isLastEqual) { return minDistance(shortStr1, shortStr2); } else { const shortStr1Cal = minDistance(shortStr1, str2); const shortStr2Cal = minDistance(str1, shortStr2); const updateCal = minDistance(shortStr1, shortStr2); const minShort = shortStr1Cal <= shortStr2Cal ? shortStr1Cal : shortStr2Cal; const minDis = minShort <= updateCal ? minShort : updateCal; return minDis + 1; }}; // let result = minDistance('horse', 'ros'); console.log(result); // 3 result = minDistance('intention', 'execution'); console.log(result); / / 5

Dynamic programming

The above recursive scheme submitted to LeetCode will timeout directly because the complexity is too high, exponentially. Let’s go back to our dynamic programming scenario, which, like the previous one, requires a two-dimensional array to store the results of each execution.

const minDistance = function(str1, str2) { const length1 = str1.length; const length2 = str2.length; if(! length1) { return length2; } if(! length2) { return length1; } str2 const r = []; str2 const r = []; for(let i = 0; i < length1 + 1; i++) { r.push([]); for(let j = 0; j < length2 + 1; j++) { if(i === 0) { r[i][j] = j; } else if (j === 0) { r[i][j] = i; } else if (str1 = = = str2 [I - 1] [1]) {/ / attention to subscript, I, j, including an empty string, the length will be the big 1 r [I] [j] = r [1] [I - 1]. } else { r[i][j] = Math.min(r[i - 1][j ], r[i][j - 1], r[i - 1][j - 1]) + 1; } } } return r[length1][length2]; }; // let result = minDistance('horse', 'ros'); console.log(result); // 3 result = minDistance('intention', 'execution'); console.log(result); / / 5

The above code is double looping, so the time complexity is $O(mn)$.

conclusion

The key to dynamic programming is to find a recursion, and with this recursion we can solve it recursively, and we can use dynamic programming. With recursion the time complexity usually increases exponentially, so we have dynamic programming. The key point of dynamic programming is to calculate from small to large, and to record each computed value, so that when we calculate a large value, we can directly take the previously calculated value. Dynamic programming can greatly reduce the time complexity, but adding a data structure to store the results of the calculation increases the spatial complexity. It’s kind of a space-for-time strategy.

At the end of this article, thank you for spending your precious time reading this article. If this article gives you a little help or inspiration, please do not hesitate to give your likes and GitHub stars. Your support is the motivation for the author to continue to create.

Welcome to my public accountThe big front end of the attackThe first time to obtain high quality original ~

“Front-end advanced knowledge” series of articles source address:https://github.com/dennis-jiang/Front-End-Knowledges