Shulou(Shulou.com)06/03 Report--

This article mainly introduces "what is dynamic planning". In daily operation, I believe that many people have doubts about what is dynamic planning. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about "what is dynamic planning"! Next, please follow the editor to study!

What is dynamic programming?

Dynamic programming, English: Dynamic Programming, referred to as DP, if a problem has many overlapping sub-problems, the use of dynamic programming is the most effective.

Therefore, each state in dynamic programming must be derived from the previous state, which is distinguished from greed, which has no state derivation, but selects the optimal one directly from the local.

When it comes to greedy algorithms, you should know this! I gave an example of a knapsack problem.

For example, there are N items and a backpack with a maximum weight of W. The weight of the first item is weight [I], and the value obtained is value [I]. Each item can only be used once to find out which items are loaded into the backpack with the greatest total value.

In dynamic programming, dp [j] is derived from dp [j-weight [I]], and then max (dp [j], dp [j-weight [I]] + value [I]) is taken.

But if you are greedy, you will be done by choosing the largest or smallest one each time, which has nothing to do with the previous state.

So greed can not solve the problem of dynamic planning.

As a matter of fact, we do not have to make a theoretical difference between dead buckle rules and greed, and the topic will be known naturally.

And many articles on dynamic planning will talk about the optimal substructure and overlapping subproblems, which are the upper definition of textbooks, obscure and impractical.

We all know that the moving gauge is derived from the previous state, and greed is the local direct selection of the best, which is enough for doing exercises.

The knapsack problem mentioned above will be explained in detail.

Problem-solving steps of dynamic programming

When making a moving topic, many students will fall into a misunderstanding, that is, they think that they will memorize the state transfer formula, change it according to the gourd, and then begin to write code. even after AC the title, they are not very clear about what dp [I] means.

This is a kind of hazy state, and then give the question, encounter a little more difficult, may not directly, and then look at the solution, and then continue to follow the gourd into this vicious circle.

The state transition formula (recursive formula) is very important, but the dynamic gauge is not only the recursive formula.

For the dynamic planning problem, I will break it down into the following five steps, these five steps are clear, can we say that we have really mastered the dynamic planning!

Determine the meaning of the dp array (dp table) and the subscript

Determine the recursive formula

How to initialize the dp array

Determine the traversal order

Derivation of dp array by example

Some students may wonder why they should first determine the recursive formula and then consider initialization.

Because in some cases, the recursive formula determines how the dp array is initialized!

In the following explanation, I focus on these five points.

Students who may have brushed the dynamic programming topic may know the importance of the recursive formula and feel that the problem will be solved once the recursive formula is determined.

In fact, determining the recursive formula is only a step in solving the problem!

Some students know the recursive formula, but they don't know how to initialize the dp array, or the correct traversal order, so that they can write down the formula, but no matter how the program is changed.

If you explain in the later order, you will gradually feel the importance of these five steps.

How should dynamic programming debug

I believe that most of the students do this on the subject of moving rules.

Take a look at the solution, feel understand, and then follow the gourd painting, if you can just draw right, everything will be fine, once you do not pass, how can not be changed, the initialization of the dp array, recursive formulas, traversal order, in a black box understanding state.

It's normal to write something wrong with the code.

The best way to find a problem is to print out the dp array and see if you deduced it according to your own ideas!

Some students for dp learning is a black box state, but do not know the meaning of the dp array, do not understand why so initialized, recursive formula memorized, traversal order depends on habit to write the code, and then write the code, if the code can pass, if not, then change it according to the feeling.

This is a very bad habit!

Before writing the code, be sure to transfer the state to the dp array to simulate the specific situation, and make sure that the final result is the desired result.

Then write the code, and if the code fails, print the dp array to see if it is different from what you deduced in advance.

If the print is the same as your own pre-simulation derivation, then there is something wrong with your own recursive formula, initialization, or traversal order.

If it is not the same as your own pre-simulation, then there is something wrong with the details of the code implementation.

This is a complete thinking process, not once the code goes wrong, there is no clue to change the East and the West, and finally can not pass, or muddle-headed.

This is why I emphasize the importance of deducing dp arrays in the five steps of moving compass.

For example, in the WeChat group of the "Code Random recording" exercise team, some users may not pass the code and will throw the code into the discussion group and ask: my code here is exactly the same as the solution, why can't I pass it?

In fact, you can think about these three questions before you ask such questions:

Did I give an example to derive the state transfer formula for this problem?

Did I print the log of the dp array?

Is the dp array printed out the same as I thought?

If the soul asks himself three questions, basically the problem will be solved, or know more clearly what he doesn't understand, whether the state transfer doesn't understand, or whether the implementation code doesn't know how to write it, or doesn't understand the order of traversing the dp array.

Then ask questions, the purpose is very strong, the friends in the group can also quickly know the questioner's doubts.

Note that this is not to say that you are not allowed to ask questions, but that you should have your own thinking before asking questions, and the questions should be to the point!

After you work, you will find that, especially in large factories, asking questions is a professional job, yes, asking questions should also reflect professionalism!

If you ask colleagues very unprofessional questions, colleagues will be lazy to answer, and leaders will think that you lack the ability to think, which is very disadvantageous to the development of the workplace.

So when we are doing exercises, we should exercise ourselves and form the good habit of asking professional questions.

At this point, the study of "what is dynamic planning" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.