According to the beginning of the article, dynamic programming solves the whole problem by solving one small problem after another. Therefore, we usually create an array or table to record the process of solving each small problem, so that we can clearly see the process of solving the whole problem.

Creating a table is done by nesting arrays within arrays, assuming we need a table like the one shown below

We just need to nest an array within an array

[
	[true, true, false, true],
	[false, false, true, true],
	[true, false, false, false],
	[false, false, false, true]
]
Copy the code

• 1
• 2
• 3
• 4
• 5
• 6

Our next three examples will also use tables like this again and again, so be sure to understand

The Fibonacci sequence is the most classic example of recursion, and the code is extremely simple to write

function fibonacci1(n) {
	if(n == 1 || n == 2) return 1;
	return fibonacci(n - 1) + fibonacci(n - 2)
}
Copy the code

• 1
• 2
• 3
• 4

The seemingly simple code, in fact, there are many internal shortcomings, we can use the tree structure to analyze the recursive process, assuming that we want to obtain the sixth number in the Fibonacci sequence, the recursive process is shown in the figure below

Obviously, in the recursion process, many values are evaluated more than once, such as 4 and 3. If we want to obtain a number larger than 6, the phenomenon of repeated evaluation will be more obvious, which is undoubtedly very costly, so we can eliminate this phenomenon through dynamic programming.

Suppose we want to get the NTH value of the Fibonacci sequence, we can first create an array, starting with the first number, in which we record the value at each index position

Function fibonacci2(n) {// let arr = [1, 1] // for(let I = 2; i < n; I ++) {arr[I] = arr[i-1] + arr[i-2]} return arr[n-1]}Copy the code

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

This method is the simplest dynamic programming, that is, through the form of an array to record the value of each small problem in the process of solving the Fibonacci sequence of the big problem, and finally we can directly obtain the value we want through the array.

Because it doesn’t have the disadvantage of repeated evaluation, it’s definitely more efficient than recursion, and we can verify that

Console. log(fibonacci1(40)) console.log(fibonacci1(40)) let end1 = date.now ( Let start2 = date.now () // console.log(fibonacci2(40)); Let end2 = date.now () console.log(' recursive elapsed time: ${end1-start1} ms dynamic elapsed time: ${end2-start2} ms'); /* 102334155 102334155 recursion time: 2476 msCopy the code

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25

It is clear from the result that the 40th value alone is nothing for dynamic programming, and the time used is almost zero, whereas the recursion takes more than 2s due to repeated evaluation. Right

Let’s start with the problem requirement: We have two strings, Raven and havoc, and now we’re going to wrap a function that gets all the largest public substrings of both strings. The result is that the largest public substring is AV, and the largest public substring is of length 2

When you first look at this problem, I think the way you usually think about it is the same as the diagram



But this is a simple and crude, the method of code is used to implement it, will also have a lot of repeated comparison between parts, so we can also use dynamic programming to solve the way to create a table, used to record the first string of each character with the second string each character of the comparison results, Finally, the maximum common substring and the length of the maximum common substring are judged by observing the table

Suppose we have two strings, abaccd and badacef, and we want the largest common substring of both

You can start by creating an 8 by 7 table, as shown

The row header represents the NTH character of the first string; The header of the column represents the MTH character of the second string

So a row header or column with a header of 0 should all correspond to a grid of 0, since the string has no 0th character, at least starting from the first, resulting in the following:

From left to right, it means that the first character of the first string is compared with each character of the second string. If they are not the same, 0 will be filled in the corresponding grid, indicating that the length of consecutive identical characters is 0. If they are the same, look at the number in the upper-left corner of the cell firstnWhat is it? And then fill it inn + 1

Why do I fill this cell with a number that is 1 greater than the value in the upper left corner when it’s the same? Because the upper-left grid represents the continuous length of the same character before the current character of the first string compared to the current character of the second string

Let’s take a look at the first line:

The second line compares the second character of the first string to each character of the second string, as shown below:

The third line compares the third character of the first string to each character of the second string, as shown below:

In the above in the process of the third line to fill in the first third character string and the second character is the second string at the same time, we checked the values in the upper left corner of the grid, the judgment of the first character of the current character of the former one character at a time and before the second character of the current character of a character comparison after continuous length is how many characters

The filling process of the remaining three lines is as follows:

The final table is shown below:

As can be seen from the table, the maximum common substring length is 2. There are two common substrings of length 2, which are the second to the third character of the first string and the third to the fourth character of the first string, i.eba 和 ac

Based on the above method, let’s encapsulate the function to find the largest common substring in code

Function publicStr(s1, s2) {// create a table let table = [] // let Max = 0 // for(let I = 0; i <= s1.length; i++) { table[i] = [] for(let j = 0; j <= s2.length; If j++) {/ / header or list head to 0, fill in grid 0 if (I = = 0 | | j = = 0) table [I] [j] = 0; Else if(s1[i-1]! == s2[j - 1]) table[i][j] = 0; Table [I][j] = table[i-1][J-1] +1 if(table[I][j] > Max) Max = table[I][j]}} let items = [] for(let I = 0; i < s1.length; i ++) { let current = table[i] for(let j = 0; j < s2.length; J + +) {if (current [j] = = = Max) items. Push (I)}} to the console. The log (` most architectural string length is ${Max} `); Console. log(' substrings of length ${Max} have: '); for(let i in items) { let start = items[i] - max console.log(`${s1.slice(start, start + max)}`); }}Copy the code

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44

Let’s use the above example to verify that this function is correct, and I printed out the result of the table so that you can check with the example to see if it is correct

Let s1 = 'abaccd' let s2 = 'badacef' publicStr(s1, s2) /* [[0, 0, 0, 0, 0, 0, 0, 0] to [0, 0, 1, 0, 1, 0, 0, 0] to [0, 1, 0, 0, 0, 0, 0, 0] to [0, 0, 2, 0, 1, 0, 0, 0] to [0, 0, 0, 0, 0, 2, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0] to [0, 0, 0, 1, 0, 0, 0, 0]] * /Copy the code

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19

The backpack question is also a very classic question. Suppose you have 4 kinds of jewelry in front of you, their weight is 3, 3, 4, 5 respectively, and their value is 4, 6, 7, 9 respectively. Now you have an item that can hold the weight of 8, how would you choose to maximize your interests?

Of course, the easiest way to do this is to write out all of the combinations, then calculate the value of each combination, and then come up with the most profitable solution

This is very simple to do recursively, and the code is as follows

Function Max (v1, v2) {return v1 > v2? v1 : V2} // Main function, used to judge the current backpack capacity, store a certain item maximum profit // parameter: Function knapsack(capacity, size, value, n) {function knapsack(capacity, size, value, n) {// If knapsack is empty or knapsack is empty, The biggest benefit to 0 if (n = = 0 | | capacity = = 0) return 0; Return knapsack(capacity, size, value) else if(size[n-1] > capacity) {return knapsack(capacity, size, value); N - 1)} // The weight of item n is less than the capacity of the backpack else {// There are two options: first, take the item; The second: Don't take the item // We'll take the most profitable option, Return Max (value[n-1] + knapsack(capacity-size [n-1], size, value, n-1), knapsack(capacity, size, knapsack, capacity, size, knapsack) Value, n-1))}} let capacity = 8 let size = [3, 3, 4, 5] let value = [4, 6, 7, 9] let n = 4 let res = knapsack(capacity, size, value, n) console.log(res) // 15, indicating that the maximum profit value is 15Copy the code

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30

As we said at the beginning of this article, such recursion is always not very efficient, so we will implement it with dynamic programming, and we will change the requirements, not only to figure out the maximum value, but also to know which items are taken.

Similarly, we create a table to record the maximum revenue for each item in any backpack capacity

Obviously, when the backpack capacity is zero, the maximum benefit we can get must be zero; All the rows numbered 0 in the table should be filled with 0, because this is the reference row we added and there is no item numbered 0, so the result is as shown in the figure:

Now we start from item no. 1 and judge its backpack capacity as1 ~ 8What is the maximum benefit that we can get out of the situation. Obviously, item 1 has a weight of 3, so when the backpack is less than 3, the maximum benefit is 0; When the backpack capacity is greater than or equal to 3, since no other items are considered, the maximum benefit we can get is the value of item 1, which is equal to 4, as shown in the figure below:

Then we consider item number 2 in the backpack capacity of1 ~ 8What is the maximum benefit that we can get out of the situation.

First of all, we know that the weight of item 2 is 3, so when the backpack capacity is less than 3, we cannot put item 2, then the maximum benefit at this time is equal to the maximum benefit of putting item 1 under the current backpack capacity;

When the backpack capacity is greater than or equal to 3, we can put item 2 in it, so we now have two choices: the first option is to put item 2 out of it, so we can only put item 1 in it, so the maximum benefit we get is the maximum benefit we get from putting item 1 in the backpack capacity; The second way is to put item 2, because we have already put item 2, there is only one item 1 left, so the maximum benefit at this point is equal to the value of item 2 + the maximum benefit from putting the remaining capacity of the backpack into item 1. We’re going to take the most profitable of these two scenarios

The filling process is as follows:

Then we consider item number 3 in the backpack capacity of1 ~ 8What is the maximum benefit that we can get out of the situation.

First of all know that the weight of the item 3 to 4, so when knapsack capacity is less than 4, we can’t put items 3, then we also need to consider is item 1 and item 2, from the previous step, item 2 of maximum yield was made on the basis of considering the item 1, so we only need to consider in item 2 of the biggest benefits can, Then the maximum return at this time is equal to the maximum return of item 2 in the current backpack capacity;

When the backpack capacity is greater than or equal to 4, we can put item 4, similar to the previous step, we have two choices, item 3 and no item 3

The filling result is as follows:

Similarly, the filling process of the last line is as follows:

The final filling result is shown in the figure below:

It is obvious from the table that the maximum revenue we can obtain is 15 when the backpack capacity is 8

At this point, we also need to push back to determine which items we take to get the most revenue

First, the grid corresponding to the maximum income is found as item 4, and then we judge whether the income is equal to the maximum income of the previous item (item 3). If it is, it means that item 4 is not put in. Otherwise, item 4 is added.

Why is that? Because we said that when we judge the maximum benefit of an item for a certain backpack capacity, when the item is heavier than the backpack capacity or we choose not to put the item in, the maximum benefit is equal to the maximum benefit of the previous item for that backpack capacity

So it can judge, we in the item 4, is only 8 – volume 5 = 3, so we find item 3 in knapsack capacity is equal to 3 cases the maximum gain corresponding grid, decide on a same item (item 2), the biggest benefit is equal to the grid in the largest income, current judgment as an equal, So we didn’t put item 3 in

The current backpack capacity is still 3. We found the grid corresponding to the maximum revenue of item 2 when the backpack capacity is 3, and judged that the current maximum revenue is not equal to the maximum revenue of the previous item (item 1) when the backpack capacity is 3, so we added item 2

At this time, the backpack capacity is 3-3 = 0, and no more items can be put into it. Therefore, we can conclude that we gain the most when we put item 2 and item 4, and the maximum value of profit is 15

The above explained the knapsack problem dynamic planning ideas, we use code to achieve it

Function Max (v1, v2) {return v1 > v2? V1: v2} let table = [] for(let I = 0; i <= n; I ++) {table[I] = []} for(let I = 0; i <= n; i++) { for(let j = 0; j <= capacity; J++) {/ / item sequence of 0 or knapsack capacity of 0, the biggest benefit to 0 if (I = = 0 | | j = = 0) table [I] [j] = 0; Else if(size[i-1] > j) {table[I][j] = table[i-1][j]} /* If (size[i-1] > j) {table[I][j] = table[i-1][j]} The maximum benefit is divided into two cases: the first case: do not put this article. Then the maximum income is equal to the maximum income of the last item in this backpack capacity; The second case: put this article. Then the maximum revenue is equal to the revenue of the item plus the remaining backpack capacity, Else {table[I][j] = Max (table[i-1][j], Value [i-1] + table[i-1][j-size [i-1]])}} // max_value = 0 let which = -1 // Find the maximum profit at capacity, For (let I in table) {let k = table[I][capacity] if(k > max_value) {max_value = k which = I} Let rest = capacity while(rest > 0 && which > 0) {// Let goods = [] let rest = capacity while(rest > 0 && which > 0) { Put the item; If (table[which][rest]! == table[which - 1][rest]) {goods. Push (which) rest -= size[which - 1]} which --} console.log(' backpacks' ${goods.join(',')} '); }Copy the code

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60

Let’s use the above example to verify the correctness of the encapsulated function. In order to facilitate verification, I also printed the table in the code, which can be compared with the final filled table in the previous example

Let size = [3, 3, 4, 5] let value = [4, 6, 7, 9] let capacity = 8 let n = 4 knapsack(capacity, size, value, n) /* The maximum income of the backpack is 15, and the items taken are 4 and 2 in Table: [[0, 0, 0, 0, 0, 0, 0, 0, 0] to [0, 0, 0, 4, 4, 4, 4, 4, 4], [0, 0, 0, 6, 6, 6, 10, 10, 10], [0, 0, 0, 6, 7, 7, 10, 13, [0, 0, 0, 6, 7, 9, 10, 13, 15]] */Copy the code

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

As you can see, by using dynamic programming to solve the backpack problem, we can clearly see the whole problem solving process, and we can also know which items were put in to get the most benefit by way of backtracking

Advanced algorithms in the application of dynamic programming here, [data structures and algorithms] this column at the end of the only article, namely greedy algorithms, I will be issued later, but also hope that we continue to pay attention to, more support ~

You can follow me, and I will always update other data structures and algorithms for you to study, and I will put these articles in the “Data Structures and Algorithms” column for you to study and use.

Then you can pay attention to my wechat official account: Front Impressions. After this column is finished, I will put notes on each data structure and algorithm on my official account, where you can go to get them.

Or you can go to my Github to get the complete code, please click Star

• Github.com/Lpyexplore/…

Creation is not easy, like to add a attention, click a collection, give a thumbs-up ~