The article directories

      • What is dynamic programming
      • Dynamic programming solution steps
      • How should dynamic programming be debugged
      • conclusion

What is dynamic programming

Dynamic Programming (DP) is most effective if a problem has many overlapping subproblems.

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

Here’s what you should know about greedy algorithms! I gave an example of the backpack problem.

For example, there are N items and a backpack that can carry up to W weight. The ith item’s weight is weight[I] and the resulting value is value[I]. Each item can only be used once to figure out which items to put into the backpack with the maximum sum of items.

Dp [j] in dynamic programming is derived from DP [j-weight[I]], and then Max (dp[j], dp[j-weight[I]] + value[I]).

But if you are greedy, each time you pick the largest or the smallest item, you are done, and it does not matter in the previous state.

So greed is not going to solve the dynamic programming problem.

In fact, we do not have to kill the difference between rules and greedy theory, do the topic behind nature will know.

And a lot of the articles on dynamic programming are going to talk about optimal substructures and overlapping subproblems and things like that, which are textbook definitions, which are hard to understand and not very practical.

We know that the moving gauge is derived from the previous state, and greedy is local directly choose the best, for brush problem is enough.

The backpack problem mentioned above will be explained in detail later.

Dynamic programming solution steps

When doing dynamic rule problems, many students will fall into a mistake, that is, they think that the state transition formula is memorized, copy and change, and start to write code, even after the topic AC, are not very clear what dp[I] represents.

It’s kind of a nebulous state, and then you go over the problem, and if it’s a little bit harder, you don’t know it, and then you look at the problem, and then you keep doing the same thing and you get stuck in this vicious cycle.

The state transition formula (the recursive formula) is important, but the dynamic gauge is more than just the recursive formula.

For the dynamic programming problem, I will break down into the following five steps, these five steps are clear, can say that the dynamic programming really master!

  1. Determine dp array (DP table) and the meaning of the subscript
  2. Determine the recursion formula
  3. How is a DP array initialized
  4. Determine the traversal order
  5. Derive dp arrays by example

Some of you might be wondering why do you decide on the recursion formula first, and then think about initialization?

Because in some cases it is the recursive formula that determines how the DP array is initialized!

I’m going to focus on these five points for the rest of the lecture.

Those of you who have done dynamic programming probably know the importance of recursive formulas, and feel like you’ve solved the problem by determining the recursive formulas.

In fact, determining the recursion formula is just one step in solving the problem!

Some students know the recursion formula, but can’t figure out how to initialize dp arrays, or the correct order of traversal, so that they can memorize the formula, but write programs that can’t be changed.

You will gradually feel the importance of these five steps.

How should dynamic programming be debugged

I believe that the topic of moving rules, a large part of the students are doing so.

If I get it right, I’m fine, but if I don’t get it right, I can’t get it right. The initialization of dp array, the recursion formula, the traversal order, I’m in a black box state of understanding.

Write dynamic topic, code problems are very normal!

The best way to find the problem is to print out the DP array and see if it follows your reasoning!

Some students learn DP in the state of black box, but do not know the meaning of DP array, do not understand why the initialization, recursion formula memorized, traversal sequence is written in this way by habit, and then write the code, if the code can pass, all is well, if not, they can change by feeling.

This is a very bad habit!

Before writing the code, you must transfer the state to the DP array to simulate the specific situation again, and make sure that the final product is the desired result.

Then write the code, and if the code doesn’t pass print out the DP array to see if it’s different from what you deduced beforehand.

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

If it is not the same as what you have simulated in advance, then the code implementation details are wrong.

This is a complete thought process, rather than just messing around and failing, or muddling through, when something goes wrong.

That’s why I stressed the importance of deriving dp arrays in the five steps of the dynamo.

For example, in the wechat group of “Code Random Thoughts”, some recording members may fail to pass the code, so they will throw the code into the discussion group and ask: why can’t I pass the code because the code here is exactly the same as the solution of the question?

Here are three questions you can ask yourself before asking:

  1. Did I derive the state transition formula for this problem by example?
  2. Did I print the dp array log?
  3. I’m printing out the DP array is that what I think it is?

If you can do all three of the soul’s questions, you can basically solve the problem, or you can clearly know what you don’t understand, whether it is the state transition, or the implementation code does not know how to write, or do not understand the order of traversing dp array.

Then ask the question, the purpose is strong, the group partners can quickly know the questioner’s doubts.

Note that this does not mean that you should not ask questions, but that you should think before you ask questions, and ask the right questions!

We will find after work, especially big factory, asking questions is a professional work, yes, ask questions to reflect the professional!

If you ask your colleagues unprofessional questions, they will be lazy to answer, and your boss will think you lack thinking ability, which is very bad for the career development.

So when we brush the questions, we will exercise ourselves and develop the good habit of professional questions.

conclusion

This chapter is an overall overview of dynamic programming, explaining what dynamic programming is, how to solve the problem, and how to debug it.

Dynamic programming is a big field, and today’s article is about some of the theoretical foundations that will be used throughout the series.

In the later explanation, the corresponding theoretical basis of a specific problem will be explained. For example, the 01 backpack in the backpack problem, the topic in Leetcode is the application of 01 backpack, but there is no pure 01 backpack problem, so the corresponding theoretical knowledge needs to be explained.

You’ll notice that the theoretical basis for this is not the definition of dynamic programming, the convoluted formula that you see in textbooks.

Here the theoretical basis is already very partial practical, every knowledge point is very useful content in the actual combat of solving problems, we should pay attention to ha.