Dynamic Programming Methodology

dynamic programming

Dynamic programming, English: Dynamic Programming, abbreviated DP, is most effective when a problem has many overlapping subproblems.

So each state in dynamic programming must be derived from the previous state, theThis is distinguished from greedthat greed has no state derivation, but rather picks the optimum directly from the localized

I give here a typical problem of dynamic programming - the knapsack problem:

For example, there are N items and a backpack that can carry a maximum weight of W. The ith item is weight[i] and the value obtained is value[i] . The weight of the ith item is weight[i] and the value obtained is value[i] .Each item can only be used once, solve for which items will be packed into the backpack with the greatest sum of item values.

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 what if it's greed, each time you take an item pick the largest or smallest and you're done, no relation to the previous state.

So greed doesn't solve the problem of dynamic programming.

And a lot of articles on dynamic programming talk about optimal substructures and overlapping subproblems, which are textbook definitions that are obscure and impractical.

As you know the kinetic gauge is derived from the previous state, and the greedy is a localized and direct selection of the optimum, which is enough for brushing up on the problem.

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

Steps to Solve Dynamic Programming Problems

When doing the topic of dynamic regulation, many students will fall into a misunderstanding, that is, thought to memorize the state transfer formula, change it according to the gourd, and then start to write the code, and even after the topic of AC, it is not quite clear what the dp[i] represents.

This is a kind of hazy state, and then give the question over, encounter slightly more difficult, may not directly, and then look at the problem solution, and then continue to follow the zucchini into this vicious circle。

State transfer formulas (recursive formulas) are important, but there is more to the moving gauge than just recursive formulas.

Dynamic Planning in Five Parts

For the dynamic programming problem, I'll break it down into the following five-step process, which you can only say you've really mastered dynamic programming once you've got all five steps figured out!

1. Determine the state variable dp and the meaning of dp
2. Determine the recurrence formula
3. How dp arrays are initialized
4. Determine the traversal order
5. Example derivation of dp arrays

Some students may wonder why it is necessary to determine the recursive formula first and then think about initialization.

Because some cases it is the recursive formula that determines how the dp array is to be initialized!

Determine the state variable dp

• In dynamic programming, a step of the state dp, is certain to be introduced by the previous state, or the state of the back, so that we must understand the dp array in the end on behalf of what it means is very important, if you do not understand a question of the meaning of the dp array is, then we can not say that we mastered the question!
• So the state variable dp is very important!

recurrence formula

I've centered the latter part of the presentation around these five points.

Students who may have brushed up on the topic of dynamic programming may be aware of the importance of the recursive formula, and feel that after determining the recursive formula the topic is solved.

In fact, determining the recurrence formula is just one step in the solution!

Some students know the recursive formula, but can't figure out how the dp array should be initialized, or the correct traversal order, so much so that they write down the formula, but can't pass the program they write how to change it.

You will slowly feel the importance of these five steps in the back order of the explanation.

How dynamic programming should be debugged

I believe that the topic of moving rules is done by a large majority of students.

Look at the problem solution, I feel that I understand, and then draw a gourd, if you can just draw the right, everything is fine, once if you do not pass, how to change can not pass, the initialization of the dp array, recursive formulas, traversal of the order of the dp array, in a kind of black-box understanding of the state.

It's not unusual to have problems with the code when writing a moving gauge topic!

The best way to find the problem is to print out the dp array and see if it's actually derived along your own lines!

Some students for the study of dp is a black box state, is not clear about the meaning of dp array, do not understand why so initialized, recursive formula memorized, traversal of the order by habit is so written, and then a drum to write out the code, if the code can be passed by all is well, if you can not pass the words by the feeling of a change.

It's a very bad habit!

To do the topic of moving rules, before writing the code, be sure to simulate the state transfer on the dp array of the specific case, the heart of the matter, to make sure that the final introduction of the desired results。

Then write the code, and if the code doesn't pass print the dp array and see if it's not the same as what you've deduced in advance somewhere.

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

If it's not the same as what you deduce from your own pre-simulation, then there's a problem with the details of the code implementation.

This is a complete thought process, rather than changing things around without a clue once something goes wrong with the code and you end up not passing, or passing in a confused manner。

This is why I emphasized the importance of deriving dp arrays in the five steps of the moving gauge.

For example: some students may not be able to pass the code, the code will be thrown to the discussion group to ask: I have been here and the code is exactly the same as the problem solution, why can not pass it?

Before posting such a question, you can actually think about these three questions for yourself:

• Did I give an example of deriving a state transfer formula for this question?
• Did I print the log of the dp array?
• Does the dp array print out the way I think it should?

If you do all three of these soul questions on your own, you've basically solved the problem!, or a clearer idea of what exactly you don't understand, whether it's the state transfer you don't understand, or the implementation code you don't know how to write, or the order in which you don't understand traversing the dp array.

summarize

• This one is a general overview of dynamic programming, explaining what it is, the steps to solving dynamic programming problems, and how to debug.

• Dynamic programming is a big field, and this one today explains some of the theoretical foundations that are used throughout the dynamic programming series.

• In the latter order to explain a specific problem, will also explain its corresponding theoretical foundations, such as the 01 backpack in the backpack problem, leetcode on the topic are 01 backpack application, and there is no pure 01 backpack problem, then you need to be in the corresponding theoretical knowledge to explain a little.

• I will also be updating a lot of classic questions on dynamic programming and how to solve them later on.

Noted:

• This post draws on the author'sCode RandomizerThe thought process and some of the original articles, to go deeper, you can move to the original author's article:Code Randomizer ()