Dynamic programming is a common algorithm, many friends feel difficult to understand, in fact, if you master his core ideas, and a lot of practice can still master. Let’s talk about dynamic programming from the beginning.
The Fibonacci series
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
Copy the codeWith the formula above, it is easy to write 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
Copy the codeNow let’s think about the above calculation process. When we calculate f(5), we need the values of f(4) and f(3), and when we calculate f(4), we need the values of f(3) and f(2), so f(3) is evaluated twice. Given that we know f(1) and f(2), we actually only need to calculate F (3), f(4) and f(5) three times. However, we can see from the figure below that in order to calculate F (5), we calculate a total of eight other values, in which f(3), f(2) and f(1) are repeated several times. If n is not 5, but a larger number, the number of computations increases exponentially, the time of this recursive algorithm is O(2n)O(2^n)O(2n).
A non-recursive Fibonacci sequence
To solve the exponential time complexity above, we can not use a recursive algorithm, but a normal cyclic algorithm. How do you do that? We simply add an array containing the value of each item. To make the array correspond to the subscript of f(n), we fill the beginning of the array with a 0:
const res = [0.1.1];
f(n) = res[n];
Copy the codeAll we need to do is fill the res array with values and return the value of 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
Copy the codeThere’s no double counting, because we’re storing the result in an array, and when you compute f(n), you just take f(n-1) and f(n-2) out of it, because you’re going to do it from small to large, so f(n-1) and F (n-2) before you do it. This algorithm has O(n) time, which is much better than O(2n)O(2^n)O(2n). This algorithm actually uses the idea of dynamic programming.
Dynamic programming
Dynamic programming has the following two characteristics
- Optimal substructure: a problem of size N can be solved by transforming it into a subproblem of smaller size. In other words, f(n) can be solved by a recurrence of a smaller scale, which is f(n) = f(n-1) + f(n-2) in the Previous Fibo sequence. Generally, problems with this structure can also be solved by recursion, but the complexity of recursion is too high.
- Overlap of subproblems: if we use recursion to solve, there will be a lot of repeated subproblems, dynamic programming is to trim the repeated calculation to reduce time complexity. But space complexity increases because of the need to store intermediate states.
In fact, the difficulty of dynamic programming is to generalize the recursion, and in the Fibonacci sequence, the recursion is given, but more often the recursion is summed up by ourselves.
Steel bar cutting problems
Let’s see how brute force works. Take a steel bar of length 5:
In the figure above, the red position indicates the position where the knife can be cut. Each position can be cut or not cut, and there are 24=162^4 = 1624=16 kinds in total. For a steel strip of length N, this situation is 2N −12^{n-1} 2N −1 kinds. Instead of writing code for the exhaustive method, let’s go straight to the recursive method:
Recursive scheme
Take the steel bar with length 5 above as an example. If we only consider cutting one cut, the position of the cut can be any position among 1, 2, 3, and 4, then after cutting, the lengths of the left and right sides are respectively:
[1, 4]: 1 position [2, 3]: 2 position [3, 2]: 3 position [4, 1]: 4 positionCopy the codeIt divides into two parts, the left and right parts can be cut again, one cut for each part, it becomes two parts again, it can be cut again. This is a problem of length five, divided into four small problems, so the optimal solution is the largest of the four small problems, and don’t forget that we can not cut at all, this is the fifth small problem, the answer we want is actually the maximum of the five small problems. The formula can be written as: For a steel strip of length N, the optimal profit formula is:
- Rnr_nrn: represents the maximum profit of the steel bar with length N as the target of our solution
- Pnp_npn: indicates that the steel bar is not cut at all
- R1 + RN − 1R_1 + R_ {n-1} R1 + Rn −1: indicates that it is cut at the position of 1, and is divided into two ends of length 1 on the left and n-1 on the right. Their sum is the optimal benefit of this scheme
- Our greatest benefit is to not cut and cut and find the maximum in the subsolutions of different cases
The above formula can already be solved recursively:
const p = [0.1.5.8.9.10.17.17.20.24.30]; // The subscript represents the length of the steel bar, and the value represents the corresponding price
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
Copy the codeThe 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, If you cut both sides, you actually double count. The first cut of length 9, the left value must be 1 — 9, we cut from 1, if we continue to cut the left value, then the left value that we continue to cut must be one of the left values we calculated earlier. For example, if you cut 5, 4 into 2, 3, 4, that’s the same thing as if you cut 2, 7 the first time, if you cut 3, 6 the first time, if you keep cutting to the left, 1, 2, 6, that’s the same thing as 1, 8, that’s what you did when you cut to the left. So if we cut the left hand side from 1, then we don’t have to cut the left hand side, we just have to cut the right hand side. So our formula can be simplified as:? r_n = \max_{1<=i<=n}(pi+r_{n-i}) ? Continue to implement the formula recursively:
const p = [0.1.5.8.9.10.17.17.20.24.30]; // The subscript represents the length of the steel bar, and the value represents the corresponding price
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); // 结果还是返回 25
Copy the codeThe above two formulas are both recursive and exponential, so let’s talk about dynamic programming.
Dynamic programming scheme
The formula of the dynamic programming scheme is the same as the previous one, we use the second simplified formula:? r_n = \max_{1<=i<=n}(pi+r_{n-i}) ? Dynamic programming is you don’t recurse, you compute from the bottom up, and every time you compute the top value, you compute the bottom value, and you just use it. So we need an array to record the maximum payoff for each length.
const p = [0.1.5.8.9.10.17.17.20.24.30]; // The subscript represents the length of the steel bar, and the value represents the corresponding price
function cut_rod3(n) {
let r = [0.1]; // the r array records the maximum return for each length
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); // 结果还是返回 25
Copy the codeWe can also type out the r array and let’s see, this stores the maximum return for each length:
r = [0.1.5.8.10.13.17.18.22.25]
Copy the codeThe use of dynamic programming reduces the exponential complexity of recursion to that of a double loop, O(n2)O(n^2)O(n2).
Output optimal solution
Although the dynamic programming above calculates the maximum value, we do not know what the corresponding cutting scheme is. In order to know this scheme, we also 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. When we backtrack, we take the left length of the target value, and then we go back to the array to find the left cut length of the optimal solution. Suppose the array of our left records is:
leftLength = [0, 1, 2, 3, 2, 2, 6, 1, 2, 3]
Copy the codeWe require the best cutting scheme for steel bar of length 9:
1. Find leftLength[9] and find that the value is 3. Record 3 as a cut 2. After cutting 3 on the left, there is still 6 left on the right. Then go to leftLength[6] and find that the value is 6. Record 6 as the length of a cut 3. After cutting another 6, we find that we still have 0 left, so we're done, and the loop ends; If there are steel bars left, continue to cut in this way. 4. The best output length is [3, 6].Copy the codeThe transformation code is as follows:
const p = [0.1.5.8.9.10.17.17.20.24.30]; // The subscript represents the length of the steel bar, and the value represents the corresponding price
function cut_rod3(n) {
let r = [0.1]; // the r array records the maximum return for each length
let leftLength = [0.1]; // Array leftLength records the length of the left when cutting once
let solution = [];
for(let i = 2; i <=n; i++) {
let max = p[i];
leftLength[i] = i; // initialize the left side to a whole block without cutting
for(let j = 1; j <= i; j++) {
let sum = p[j] + r[i - j];
if(sum > max) {
max = sum;
leftLength[i] = j; // Each time a large value is found, record the length to the left
}
}
r[i] = max;
}
// Backtrack to find the best solution
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]}
Copy the codeLongest Common Subsequence (LCS)
The problem can also be solved by brute force enumerating all the substrings of the X string first, assuming that its length is M, there are a total of 2m2^m2m kinds of situations, because for each character in the X string has two states of keeping and not leaving, the total permutation of M characters is 2m2^m2m kinds. The corresponding Y string has a 2n2^n2n substring, where n is the length of Y. And then I iterate over it to find the longest common subsequence, which is very complicated, so I’m not going to write it here.
We look at two strings, and if they have the same last character, their LCS (short for longest common subsequence) is the LCS of both strings with the last character removed plus one. Because the last character is the same, so the last character is their subsequence, and if you take it away, the subsequence is missing one, so their LCS is the LCS of the string that they took away the last character plus one. If their last character is different, their LCS is X minus the last character and Y minus the last character, or X minus the last character and Y minus the last character, which is the longer of the two of them. The mathematical formula is:
If you look at this formula, a problem of size (I, j) becomes a problem of size (I -1, j-1), isn’t that a recursion again?
Recursive scheme
We have the formula, no nonsense, write the code directly:
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);
returnlcsShort1 > lcsShort2 ? lcsShort1 : lcsShort2; }}let result = lcs('ABBCBDE'.'DBBCD');
console.log(result); / / 4
Copy the codeDynamic programming
Recursion works, but the complexity is too high, and the time required for longer strings increases exponentially. We’re going to use dynamic programming again, and according to the principle of dynamic programming we talked about earlier, we’re going to have to go from small to large, and we’re going to write it down every time we get a value. 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 cases 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;
// Construct a two-dimensional array
// I indicates the row number, corresponding to length1 + 1
// j indicates column number, corresponding to length2 + 1
// The first row and the first column are all 0
let result = [];
for(let i = 0; i < length1 + 1; i++){
result.push([]); // Initializes an empty array for each behavior
for(let j = 0; j < length2 + 1; j++){
if(i === 0) {
result[i][j] = 0; // The first line is all zeros
} else if(j === 0) {
result[i][j] = 0; // The first column is all zeros
} else if(str1[i - 1] === str2[j - 1]) {// The last character is the same
result[i][j] = result[i - 1][j - 1] + 1;
} else{
// The last character is different
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
Copy the codeIf Xi=YjX_i = Y_jXi=Yj, then its value is the value above the slope plus one. If Xi≠YiX_i \neq Y_iXi=Yi, if Xi≠YiX_i \neq Y_iXi=Yi, It’s going to be the one on the top or the one on the left.
Outputs the longest common subsequence
To output the LCS, the idea is similar to the previous cutting steel bar, recording each step and then backtracking. To record the operation we need a two-dimensional array as large as the result two-dimensional array, and the values in each cell are where the current value came from, and of course, the first row and column are still 0. The value of each cell comes either from the top, top, or left, so:
1. We use 1 to indicate that the current value comes from the top of the slope. 2. We use 3 to indicate that the current value comes from the topCopy the codeLook at the code:
function lcs3(str1, str2) {
let length1 = str1.length;
let length2 = str2.length;
// Construct a two-dimensional array
// I indicates the row number, corresponding to length1 + 1
// j indicates column number, corresponding to length2 + 1
// The first row and the first column are all 0
let result = [];
let comeFrom = []; // Save the source array
for(let i = 0; i < length1 + 1; i++){
result.push([]); // Initializes an empty array for each behavior
comeFrom.push([]);
for(let j = 0; j < length2 + 1; j++){
if(i === 0) {
result[i][j] = 0; // The first line is all zeros
comeFrom[i][j] = 0;
} else if(j === 0) {
result[i][j] = 0; // The first column is all zeros
comeFrom[i][j] = 0;
} else if(str1[i - 1] === str2[j - 1]) {// The last character is the same
result[i][j] = result[i - 1][j - 1] + 1;
comeFrom[i][j] = 1; // The value comes from above the slope
} else if(result[i][j - 1] > result[i - 1][j]){
// The last character is different, the value is the left large
result[i][j] = result[i][j - 1];
comeFrom[i][j] = 2;
} else {
// The last character is different, the value is higher
result[i][j] = result[i - 1][j];
comeFrom[i][j] = 3; }}}console.log(result);
console.log(comeFrom);
// Backtrace the comeFrom array to find the LCS
let pointerI = length1;
let pointerJ = length2;
let lcsArr = []; // An array holds the LCS results
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"]
// Now the lcsArr order is reversed
lcsArr = lcsArr.reverse();
return {
length: result[length1][length2],
lcs: lcsArr.join(' ')}}let result = lcs3('ABCBDAB'.'BDCABA');
console.log(result); // {length: 4, lcs: "BDAB"}
Copy the codeMinimum edit distance
This is a problem in LeetCode, which is described as follows:
The longest common subsequence is the longest common subsequence. We also assume that the first string is X=(x1,x2… xm)X=(x_1, x_2 … x_m)X=(x1,x2… Xm), the second string is Y=(y1,y2… yn)Y=(y_1, y_2 … y_n)Y=(y1,y2… Yn). The target of our solution is RRR, and r[I][j]r[I][j]r[I][j] is the solution of XXX with length III and YYY with length JJJ. We also start with the last character of both strings:
- If the last character is the same, then the last character does not need to be edited, just need to know the shortest edit distance of the previous character, written in the formula: If Xi = YjXi = Y_jXi = Yj, r = r [j] [I] [I – 1] r [j – 1] [I] [j] = r [I – 1] [1] r [I] [j] = r [I – 1] [j – 1].
- If their last character is different, the last character must be edited once. The shortest edit distance is XXX remove the last character and YYY the shortest edit distance, plus the last character once; Or YYY remove the last character and XXX shortest edit distance, plus the last character once, depending on the two numbers which is smaller. Note that removing the last character in XXX or YYY is equivalent to inserting and deleting the last character in YYY. However, in addition to inserting and deleting the last character in XXX or YYY, there is also a replacement operation. If the replacement operation is performed, the length of the two strings will not be changed. Distance of r [I] [j] = r [I – 1) + 1 r [j – 1] [I] [j] = r [I – 1]] [j – 1 + 1 r [I] [j] = r [I – 1] [j – 1) + 1. The final formula is to take the minimum of these three cases and write it as: If Xi≠YjXi \neq Y_jXi=Yj, R [I] [j] = min (r [j], [I – 1] r [j – 1], [I] r [I – 1) [j] – 1) + 1 r [j] = \ [I] min (r [I – 1) [j], R [1], [I] r [I – 1]] [j – 1) + 1 r [I] [j] = min (r [j], [I – 1] r [j – 1], [I] r [I – 1) [j] – 1) + 1.
- Finally, if either XXX or YYY is an empty string, to make them the same, insert another string into the empty one. The shortest distance is the length of the other string. Mathematical formula is: if I = 0 I = I = 0, 0 r [I] [j] = jr [I] [j] = jr [I] [j] = j; If j=0j=0j=0, r[I][j]= IR [I][j]= IR [I][j]= I.
All right? 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 always, with recursion, 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; }};// Test it
let result = minDistance('horse'.'ros');
console.log(result); / / 3
result = minDistance('intention'.'execution');
console.log(result); / / 5
Copy the codeDynamic programming
Submitting the recursive scheme above to Leetcode will simply time out because of the exponential complexity. Let’s go back to our dynamic programming scheme, which, like before, 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;
}
// I is the line str1
// j is the column for 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[i - 1] === str2[j - 1]) {// Note that the subscripts, I,j include empty strings that are 1 longer
r[i][j] = r[i - 1][j - 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];
};
// Test it
let result = minDistance('horse'.'ros');
console.log(result); / / 3
result = minDistance('intention'.'execution');
console.log(result); / / 5
Copy the codeThe above code is double loop, so the time complexity is O(mn)O(mn)O(mn).
conclusion
The whole point of dynamic programming is to find recursions, and with recursions we can solve recursively, or we can do dynamic programming. With recursion time complexity usually increases exponentially, so we have dynamic programming. The whole point of dynamic programming is to go from small to large, to write down every single value that we have calculated, so that when we calculate the large value, we can directly get the value that we have calculated before. Dynamic programming can greatly reduce the time complexity, but adding a data structure to store the calculation results will increase the space complexity. It’s kind of a space-for-time strategy.
At the end of this article, thank you for your precious time to read this article. If this article gives you a little help or inspiration, please do not spare your thumbs up and GitHub stars. Your support is the motivation of the author’s continuous creation.
Welcome to follow my public numberThe big front end of the attackThe first time to obtain high quality original ~
“Front-end Advanced Knowledge” series:Juejin. Cn/post / 684490…
“Front-end advanced knowledge” series article source code GitHub address:Github.com/dennis-jian…