Comics: What is Dynamic Programming?

— — — — — —

Topic:

There is a staircase of 10 steps, from the bottom to the top, each step can only go up one or two steps. We want to use the program to figure out how many total moves there are.

For example, taking 10 steps, one step at a time, is one of the ways. We can write it as 1,1,1,1,1,1,1,1,1,1.

Let’s say you take five steps, two steps at a time. That’s another way to go. We can write this as 2,2,2,2,2.

And, of course, there are many, many other ways to go.

— — — — — —

First case:

The second case:

Let me draw it out, and it looks like this:

F(1) = 1;

F(2) = 2;

F(n) = F(n-1)+F(n-2) (n >=3)

Method 1: solve recursively

Since the code is relatively simple, I won’t go into too much detail here.

As shown in the figure, the same color indicates that the method is passed the same parameters.

Method two: memorandum algorithm

In the above code, the collection map is a memo. Each time we need to calculate F(N), we first look for matching elements from the map. If it is in the map, the result is returned directly, if not, the result is calculated and stored in the memo.

Method three: dynamic programming solution

The program iterates from I =3 until I =n. In each iteration, the number of moves of one more step is calculated. Only two temporary variables, A and B, are retained during the iteration, respectively representing the results of the last iteration and the last iteration. To make it easier to understand, I’ve introduced the temp variable. Temp represents the result value of the current iteration.

Title two: The King and the Gold Mine

In one country, five gold mines were discovered, each with a different amount of gold and a different number of workers needed to dig them. The total number of miners involved in the dig was 10. Every gold mine is dug or not dug, you cannot send half the men to dig half the gold. And it’s going to be a program to figure out, well, which mines should I dig in order to get as much gold as possible?

Method one: permutation and combination

Each gold mine has two choices: to dig or not to dig. If you have N gold mines, you have 2 to the N choices. Go through all the possibilities, eliminate those that use more than 10 workers, and find the one that gets the most gold out of the remaining options.

I’m not going to show you the simple code, and the time complexity is obvious, which is order two to the N.

F(n,w) = 0 (n<=1, w<p[0]);

F(n,w) = g[0] (n==1, w>=p[0]);

F(n,w) = F(n-1,w) (n>1, w<p[n-1])

F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w>=p[n-1])

The third is an add-on, and it’s not hard to see why.

Method two: simple recursion

To translate the state transition equation into a recursive program, the condition for the end of the recursion is the boundary in the equation. Because each state has two optimal substructures, the recursive flow of execution resembles a binary tree of height N.

The time complexity of the method is order two to the N.

Method three: memorandum algorithm

Add a HashMap memo to the simple recursion to store intermediate results. The Key of the HashMap is an object containing the number of gold mines N and the number of workers W, and Value is the number of gold obtained by the optimal selection.

The method has the same time and space complexity as the number of different keys in the memo.

Method four: dynamic programming

Methods The final result was derived step by step by using two – level iteration. In each outer iteration, that is, for each row of the table, the preResults of the previous row are retained and the results array of the current row is iterated through.

The time complexity of the method is O(n * w), and the space complexity is (w). It is important to note that when there are only five gold mines, the performance benefits of dynamic programming have not yet been realized. When there are 10 or more gold mines, dynamic programming has a clear advantage.