【 algorithm 】 Beat the drum pass flower game – dynamic programming problem solution problem solution

First, the small voice BB

Everybody listens to my BB first some experience (nonsense) let’s carry on to beat drum pass flower game ~

As a front-end engineer who was afraid of algorithms half a year ago, I started to systematically learn some algorithm knowledge recently. Although still can not master, but can clearly feel their fear of the algorithm disappeared. (Before the algorithm was like a high-level boss, even identification would fail before the system learning foundation, after the system learning foundation, the boss is still difficult to kill, but can identify his attributes), I also learned some theories about learning, summed up in the following three points (made up by myself) :

1. There’s a big gap between being able to read and being able to write

2. Simplify complex questions and become proficient in simple answers.

3. Feynman Method of learning (The real way to learn a skill is when you can teach it to someone in plain English)

The first point is actually a description of a kind of understanding, do not know the situation, I would turn over some sorting algorithm of the technical community before, read more than four or five similar articles, feel very clear when reading, but when doing the problem, there will be a kind of do not know how to write the feeling.

In fact, the reason is to understand and learn a knowledge of the two levels, and between the two need a lot of deliberate practice.

The second point is actually very helpful to the learning algorithm, although we can not win the big boss, but we can break the algorithm into small boss, small boss but then break into elite monster to fight. From the data structure, it can be divided into:

• string
• An array of
• The list
• Binary tree
• The queue
• figure
• .

From the way of solving the problem, it can be divided into:

• Depth-first search

• Breadth-first search

• Greedy algorithm

• Dynamic programming

• .

What we actually need to do is to practice these subdivided knowledge blocks, so as to learn and explore the algorithm as a whole module.

The third point is why I want to write this article. I hope to record some key nodes of my learning algorithm in the form of the article. Then try to use their own understanding to use I can understand the concept of complex language spoken, then issue to show bosses, can give some guidance criticism (don’t know if you have this kind of feeling, is the kind you learn but you don’t know if you learn what is right, a lot of knowledge of learning all the uncertainty,), It might be enlightening to show it to someone who is even greener than yourself. In the next article (if(!! Let’s play the game of flower passing

musical

Post two pictures for those who don’t know the game mechanics to understand the game mechanics, then post the title ~

For those of you with pins and needles in your scalp, let me change the problem for you, using example 1 in the problem as an example

N = 5, base = [[0, 2], [2, 1], [3, 4], [2, 3], [1, 4], [2, 0], [0, 4]], k = 3Copy the code

Said: There are 5 children playing with throwing the ball, and not all of them are on good terms. After they get the ball, they will only throw the ball to their good friends. For example, child No. 0 will only give the ball to child No. 2 and Child No. 4 (information obtained from relation array). How many ways can you throw the ball before it reaches kid number 4?

Depth-first + recursion

The first solution of the problem is to convert the whole problem into a graph to calculate the number of paths, and each element in Relation is a directed edge. Then, depth-first + recursion is used to solve the problem. We won’t go into details here, but you can see the solution if you are interested.

Dynamic Programming

According to my current understanding, dynamic programming is actually the law we are familiar with. We need to find the starting value (boundary case) and the law (dynamic transfer equation) of this law. Let’s first put aside these professional terms and first look for the law in accordance with the basic logic.

First of all, the ball is in the hand of child number zero at the beginning, when you start to drop the ball, what happens to the ball? According to the relationship between children described in Relation, we know that child no. 0, child No. 2 and child No. 4 play well, so there are only the following two situations:

1. I went from 0 to 2
2. I went from 0 to 4

So after the first round of throwing the ball, each child may get the ball in the following ways:

What about the second round? In the first round, we know that the ball may be in the hands of child No. 2 or No. 4. According to their close relation relation, we can know that friend No. 2 is no. 0, No. 1 and No. 3. Number 4 has no best friends!

So what happens when we finish round two?

What about the third round? We’ve been able to try to find this pattern from the first round and the second round. The state of each round is actually deduced from the state of the previous round and Relaiton according to some logic. This logic is actually the state transition equation, and the boundary condition is actually the initialization of our game when little player 0 holds the ball. If we use an array to store the possible values for each round, from initialization to the end of round 2 we get the following data:

[1,0,0,0,0]// before the first round, only child 0 could hold the ball [0,0,1,0,1]// before the second round, only 2,4 children could hold the ball in one way [1,1,0,1,0]// before the third round, only child 0,1,3 could hold the ball. And there's only one way to hold the ballCopy the code

Then in the third round, we can get the information of the second round, and generate the information of the third round through Relation, and deduce the information of all subsequent rounds:

for (let i = 0; i < k; i++) { for (const [from, to] of relation) { dp[i + 1][to] += dp[i][from]; [0,0,1,0,3]Copy the code

So what we need to return is the k round, which is the n-1(number 4) after the third round in the example problem. The possible way for children to get the ball is 3.

Why is this problem called dynamic programming problem solving? Because I am still learning how to use dynamic programming problem solving, and then see this problem solving time is a little bit confused, paste the official website problem solving:

For a student with poor mathematical foundation and algorithm foundation (I said myself) gives me the illusion that I can’t even copyComplex mathematical notationandThe formula(In fact, it is not complicated after understanding) actually makes it more difficult for me to understand this way of thinking. Therefore, I just want to sort out these mathematical formulas with simple logic through my own understanding. The specific reason is inWhisper BB linkAlso said, here is not wordy ~

Entertain foolish ideas

And when I bring it back to reality, it’s actually kind of interesting. For example, at the annual meeting of the company, there will also be this kind of activity of drumming and passing flowers. One thing will be passed to each other. After the music stops, whoever holds the thing will perform on stage or be punished. Relation condition shows that this activity is not a game with equal probability. To some extent, this game can reflect a person’s popularity in the social circle (such as in the company). Because the more places you are in the relation array, the more likely it is that you will end up with a ball in your hand. Hopefully, everyone can do the second place of relation

There is also recently bought a book called deliberate practice, also forget which big guy recommended. The express delivery has already arrived downstairs of the company. I will write what I feel after reading it later.

Algorithm learning is just beginning, for some people may be a four-year front-end to learn algorithms a little late, but for me, as long as I start, it is not too late ~