Explain dynamic programming in an easy-to-understand way

preface

Dynamic programming is a relatively difficult to understand algorithm ideas, this article combined with their own understanding of the use of easy to understand the way to explain dynamic programming, welcome interested developers to read this article.

Thought analysis

Next, we will analyze it step by step through an example and draw out the idea of dynamic programming.

Suppose, your home three denominations of banknotes (1 yuan, 5 yuan, 11 yuan) countless, now need to use these banknotes to raise a certain amount out, how do we need to use the least amount of banknotes to raise this amount out?

We need to scrape up 15 yuan.

Greedy thinking – looking only at the present

According to our life experience, it is certain to use a large paper bill first, with the total amount to do the subtraction operation, the idea is as follows:

Take an 11 dollar bill, and the amount we’re going to raise is4 yuan(15-11)
To gather together4 yuanCome out, we can only make it with 1 dollar bills, we need 4 1 dollar bills.4-1, 1-1, 1-1)

Fifteen dollars came together, and we used five bills altogether (one in eleven and four in ones). This strategy is called greed. We set the amount of money to be collected as W and the denomination of banknote to be used as M. The greedy strategy will make W smaller as soon as possible.

After our brain calculations, this strategy didn’t take the least amount of money to make $15. We could just use three $5 bills to make that amount.

A better solution – dynamic programming

When we use greedy thinking to solve this problem, only consider the immediate situation, the pattern is small, so how should we avoid this situation now?

If the method of violent enumeration is used to collect the amount, obviously the time complexity is too high, too many combinations can collect the amount, the enumeration time is unbearable.

Overlapping subproblem

Now, let’s try to figure out what the properties of this problem are.

At the beginning, if we take an 11, the next problem is to scrape up the minimum amount needed for a 4
At the beginning, if we take a 5, the next problem is to scrape up the minimum amount needed for a 10
At the beginning, if we take a 1, the next problem is to scrape up the minimum number of bills needed for a 14

After the above analysis, we can see that these problems have a common form: given a sum, the minimum amount of money needed to make up that sum.

We’ve broken down a big problem into three sub-problems.

Next, let’s analyze these three sub-problems again. We use F (n) to represent the minimum amount of money needed to raise N, and cost to represent the amount of money needed to raise W, then:

If we take 11, the total number of bills we end up using is:cost = f(4) + 1
If we take 5, the total amount of money we end up using is:cost = f(10) + 1
If we take 1, the total amount of money we end up using is:cost = f(14) + 1

When we look at the above problems, we find one thing in common: for each denomination, we need to calculate the minimum number of banknotes remaining, and they are all calculated in the same way.

These three subproblems all need to be solved in the same way, so they are overlapping subproblems.

Optimal substructure

When we come up with $15, we need the lowest of the three.

When we solve f(n), we also need to calculate the minimum number of bills for the amount of N, such as F (10), we can only use two denominations (5 yuan and 1 yuan).

So if we had 5 dollars, we’d need f(5) + 1
So if we had 1 dollar, we’d need f(9) + 1

When we solve f(n), we must find the solution with the least number of coins from the subproblem, i.e. :

f(n) = min(f(n – 1), f(n -5 ), f(n – 11)) + 1

The optimal solution of a large problem can be derived from the optimal solution of a subproblem, and this property is called optimal substructure.

There was no aftereffect

Through the above analysis, we know that when the amount is 15, three overlapping sub-problems need to be solved, and the optimal one is the solution of the final problem.

Those three subproblems have their own overlapping subproblems. When solving these overlapping subproblems, we only need to know the final answer, and do not care about how they are calculated, because their calculation process will not affect the subsequent problems.

For example: f(4), F (10), f(14), we only need to figure out their specific values, and their calculation process has no impact on the problems we need to solve later.

If the state of a certain stage is given, the development of the process after that stage is not affected by the state of the previous stage, it is said to have no aftereffect, that is, the future has nothing to do with the past.

Cut the rope

Take a string of length n, cut the string into m segments (m and n are integers, n > 1 and m > 1), and write the length of each segment as K [0], k[1]… , k [m].

K [m] * k[1] *… What is the largest possible product of k[m]?

For example, when the length of the rope is 8, we cut it into three lengths of 2, 3 and 3 respectively, and the maximum product we get is 18.

Thought analysis

Next, let’s look at this example and see if we can solve it with dynamic programming.

A. what B. what C. what D. what

The length of the rope must be greater than 1 and make at least one cut at a time
We use f(n) to represent the largest product of all the cuts of a rope of length n

So, when the length of the string is 2, we only have one way to cut it, from the middle, and the string will be cut into two pieces of length 1, as shown below:

When n=2, f(n) = 1 * 1 = 1, that is, f(2) = 1

Let’s move on to the n=3 case, and as you can see in the picture below, there are two cuts

Cut two pieces of length 1 and length 2
Cut three sections with length of 1, 1 and 1 respectively

From the cut method 2, we can see that it is actually a slice of the rope with length 2. After the previous analysis, we already know that the maximum product of all the cuts is 1, so their product is 1 * 1 * 1 = 1.

So, instead of dividing it, we take the product of cut method 1, that is, f(3) = 2

Let’s look at the case where n is equal to 4, as you can see in the picture below, it has three cuts

Cut two pieces of length 1 and length 3
Cut two pieces of length 2 and length 2
Cut into four pieces of equal length

So from the first cut, we can see that the maximum product of the rope length 3 we already figured out (f(3) = 2), if we cut this rope, the product gets smaller, so we choose not to cut this rope, so the maximum product of the first cut is 1 times 3, which is 3.

From cut 2, we can see that the length of the two pieces of rope is 2, and we have calculated the maximum product of the two pieces of rope (f(2) = 1). If we cut, the product becomes smaller, so the maximum product of cut 2 is 2 * 2 = 4.

To sum up, we can find a law as follows:

No matter how many lengths the rope ends up being cut, it must be cut one by one
When the rope is 2 or 3, you don’t cut it anymore, you just take the length

So, for a string, once it has been cut, it is divided into two subproblems:

How to cut the rope to the left of the cutting point
How to cut the rope to the right of the cut point

Because we started at 1 and pushed back, how do we cut the rope in front, we already saved it.

So far, we have found that it has met the two characteristics of dynamic programming:

Overlapping subproblem: After the rope is cut, it is possible for each part of the rope to be further cut, and the subproblem is the same each time the rope is cut
Optimal substructure: When we slice each part of the rope, we need to figure out what is the maximum product of all the cutting methods of this part of the rope, which satisfies the property of optimal substructure

Let’s analyze the case where n=5. As shown in the figure below, our first cut has two ways: from position 1 and position 2. The rope can be cut as:

Two segments of length 1 and length 4
Two segments of length two and three

We use an array (result) to store the maximum product (optimal solution) of the rope we have solved previously. In summary, we know that when the rope length is less than 4, the maximum product of each rope length is fixed, i.e. :

result[0] = 0
result[1] = 1
result[2] = 2
result[3] = 3

Note: Since the rope has to be cut at least once and the length of the rope is greater than 1, it cannot be cut when the length of the rope is 1, so its maximum product is 1.

When the rope is 2 or 3, we don’t slice it, so their maximum product is just their length.

Observation after above, we found that when the string length is greater than or equal to 4, the location of the first knife to cut to cut the rope length can be at most half of the position, controlling a subproblem, we has been calculated in front and in the result, we need to cut each method of maximum subproblem is multiplied by the optimal solution to take out the can.

When n=4, the positions of the first cut can be: 1, 2:

result[4] = max(result[1] * result[3], result[2] * result[2])
          = max(1 * 3, 2 * 2)
 			    = max(3, 4)
          = 4
Copy the code

When n=5, the positions of the first cut can be: 1, 2:

result[5] = max(result[1] * result[4], result[2] * result[3])
	        = max(1 * 4, 2 * 3 )
          = max(4, 6)
          = 6
Copy the code

When n = 6, the positions of the first cut can be 1, 2, and 3

result[6] = max(result[1] * result[5], result[2] * result[4], result[3] * result[3])
					= max(1 * 6, 2 * 4, 3 * 3)
					= max(6, 8, 9)
					= 9
Copy the code

So far, we can find that when we seek the optimal solution of the sub-problem, we only care about its result, and its calculation process does not affect the solution of our final problem, so it also meets the last property of dynamic programming: no aftereffect

The recursive formula

After a series of deduction above, we find that this problem has met the three properties of dynamic programming, that is to say, this problem can be solved by dynamic programming.

After the above analysis, we know that no matter how we cut it, the rope will be cut into two parts, and then solve for the maximum product of the two parts respectively, so when the length of the rope is N, we can get the following formula:

result[n] = result[i] * result[n - i]

N is the required rope length, and I is the current position to be cut.

No matter where the rope is cut, it’s going to be cut into two pieces, and we’re going to take the product of these two pieces, and we’re going to take the maximum product of each of these cuts and we’re going to take the maximum product of the rope of length N.

The implementation code

Now that we know how to solve this problem, we can implement it in TypeScript code like this:

public cutTheRope(length: number) :number {
    // Since the rope can only be cut in whole numbers, it cannot be cut if the rope length is less than 2
    if (length < 2) {
      return 0;
    }
    // If the rope length is 2, you can cut only from the middle, and the maximum product of all cuts is 1
    if (length === 2) {
      return 1;
    }
    // When the rope length is 3, it can be cut into:
    // 1. 1. 1
    / / 2. 1. 2
    // 1 * 2 > 1 * 1 * 1, so when the length is 3, the maximum product of all cuts is 2
    if (length === 3) {
      return 2;
    }

    // Create the result array to store the maximum product of each length of rope cut
    const products = new Array<number>(length + 1);
    If the length is less than 4, the maximum product of the ropes has already been calculated, so it can be saved directly
    products[0] = 0;
    products[1] = 1;
    // When the rope length is 2 or 3, no splitting is performed. The maximum product is the length of the rope
    products[2] = 2;
    products[3] = 3;

    // If the length of the rope is greater than 4, the rope needs to be cut. Find the maximum product of each cut rope
    for (let i = 4; i <= length; i++) {
      // Assign an initial value
      products[i] = 0;
      // The maximum product of the current length of rope
      let max = 0;
      // Make at least one cut, starting at position 1 of the string, to position I /2.
      // Find the maximum product of two pieces of rope when length is I
      for (let j = 1; j <= i / 2; j++) {
        // Find the product of two pieces of rope according to recursive formula
        const product = products[j] * products[i - j];
        // Compare the maximum product of two lengths of rope in the historical method with the product of two lengths of rope in the current method
        if (max < product) {
          // Replace the maximum value
          max = product;
        }
        // Change the maximum product of the current rope length cutsproducts[i] = max; }}// The maximum product of each length of rope has been calculated, and the value of the length position is the solution to the whole problem
    return products[length];
}
Copy the code

DynamicProgramming. Ts

Write test cases

Let’s take the string of length 8 from the problem and plug it into the above code to find the maximum value to verify that our code is correct, as shown below:

import DynamicProgramming from ".. /DynamicProgramming.ts";

const dynamicProgrammingTest = new DynamicProgramming();
const maxVal = dynamicProgrammingTest.cutTheRope(8);
console.log("Maximum is", maxVal);

Copy the code

DynamicProgramming-test.ts

The running results are as follows:

Examples of the same type

After reading this article, you are sure to have a certain understanding of dynamic programming, and then you can try to do other problems that can be solved by dynamic programming, deepen your understanding, and achieve the purpose of thorough mastery.

I have also written several other analysis articles on dynamic programming problems, if you are interested in them, please follow:

Minimum coin change problem
Knapsack problem
Longest common subsequence
Matrix chain multiplication

Write in the last

At this point, the article is shared.

I’m an amazing programmer, a front-end developer.

If you are interested in me, please visit my personal website for further information.

If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
This article was first published in nuggets. Reprint is prohibited without permission 💌

Explain dynamic programming in an easy-to-understand way

preface

Thought analysis

Greedy thinking – looking only at the present

A better solution – dynamic programming

Overlapping subproblem

Optimal substructure

There was no aftereffect

Cut the rope

Thought analysis

The recursive formula

The implementation code

Write test cases

Examples of the same type

Write in the last

Related Posts

Pale RxJS WebSocket

The new keyword

How does Android — React — Native handle push at home and abroad