Abstract: Usually practice algorithm learning algorithm knowledge, often found in the solution of the problem written “dynamic programming”, which is a complex DP formula, for the new people in addition to say “wonderful ah”, the rest is confused, how did he think of this formula? Can I imagine? Does this thing work at all?

This article is from The huawei Cloud community “How did dynamic planning come into being?”

When I practice algorithm problems and learn algorithm knowledge, I often find that “dynamic programming” is written in the solution of the problem, which is a complex DP formula at the beginning

What’s left is the question, how did he come up with this formula? Can I imagine? Does this thing work at all? Add the fancy name “dynamic programming,” and it dissuades a lot of people from trying to understand it.

Dynamic programming sounds scary, but let’s put it another way

Internally, I prefer to call it “state caching,” which is a familiar term for service development, using caching to speed up the response to repeated requests. The characteristic of this cache is that it is associated with other caches.

For example, our service calculates a sum of money over a period of seven days, and then caches it. And then we get a request to sum up the money for 8 days and we just take the sum of the money for 7 days and add the money for 8 days.

1+4 thinking set

I summed up a thinking routine for dynamic programming. I called him 1 set of examples and 4 questions, just called 1+4. Through these 5 processes, we can understand how dynamic programming is thought from the perspective of ordinary people (i.e. non-ACM bosses)

  • Write a set of examples of how to calculate timeouts

  • Based on the timeout example, what are the repetitions and wastes?

  • How do I define dp arrays

  • What is the direction of change and how is it changing

  • What are the boundary states

A simple example

Take a simple example: climbing stairs: leetcode-cn.com/problems/cl…

At this point, take a moment to see if there is a scenario of repeated experience in the solution example, and that scenario of repeated experience is called a state. When I deal with dynamic programming problems, I ask myself three questions, and I usually get it right.

① Write a set of examples of the calculation process in the idea of timeout

So if we think about the easiest way to do it, which is to start at the beginning, take one or two steps at a time, and see if we get to the end, plus one. But this method is destined to timeout (O (n^2)), but I still follow this process simulation, random list 1-> 2-> 3->4->51-> 2-> 3-> 51->3->4->51-> 5

(2) Based on the timeout example, what are the repetitions and wastes?

Up there, I found repetition

That is to say, there are 2 routes from 3 to 5, which have been calculated after 1->2, I walk from 1 to 3 and then back, there is no need to calculate. In other words, by the time I get to 3, I already know how many ways I have left. Once you find the overlap, you can start building the DP formula.

③ How to define dp array?

Define the DP array, that is, define the repetition mentioned above. If I go back to the previous statement by the time I get to 3, I already know how many ways I have left. So dp[3] is how many ways you can go from 3.

④ What is the change direction of the state and how is it changed

  • First think about the direction in which the state is changing

Look again at this sentence:

By the time I get to 3, I can already tell how many ways I have left

So it depends on what goes back so we have to calculate what goes back first, which is going back to front

  • And then think about how does this later state relate to the current state, how does it change

This is usually included in the problem condition

I can take either 2 steps or 1 step, so every time I go to a level, I can change two states the next time. So for layer 3, he has 2 subsequent moves, 1 move or 2 moves so his situation is dp[3] = dp[3+1] + dp{3+2} if the number of layers is set to I, then the situation is dp[I] = dp[I +1] + dp[I +2].

⑤ What is the boundary state?

A boundary state is a state that doesn’t depend on the state behind it and can get the result directly. In this case it must be the last layer dp[n], which by default is a move. dp[n]=1

implementation

This state and change is defined by the procedure above

  • Definition: dp[I] : represents the number of possible moves from level I onwards

  • Dp [I] = dp[I +1] + dp[I +2];

  • Boundary: dp[n] = 1

It’s easy to write code based on this:

public int climbStairs(int n) { int[] dp = new int[n + 1]; dp[n] = 1; dp[n-1] = 1; for(int i = n-2; i >=0; i--) { dp[i] = dp[i+1] + dp[i+2]; } return dp[0]; }Copy the code

Advanced version, two dimensional dynamic programming

Leetcode-cn.com/problems/nu…

① Write a set of examples of the calculation process in the idea of timeout

The idea behind timeouts must be to simulate all walks like a search. Let’s assume 1 steps=5 and arrlen=3. Simulate the position of constant walking. The number refers to the current position. 0 – > 1 – > 2 – > 1 – > 0-1 – > > 00 – > 1 – > 2 – > 1 00 – > – > 1-1-1-1 – > > > > 00-1-1-1 – > > > > 0 – > 00 – > 0-1-1-1 – > > > > 0…

(2) Based on the timeout example, what are the repetitions and wastes?

0 – > 1 – > 2 – > 1 – > 0-1 – > > 00 – > 1 – > 2 – > 1 00 – > – > 1-1-1-1 – > > > > 00-1-1-1 – > > > > 0 – > 00 – > 0-1-1-1 – > > > > 00 – > 0-1-1 – > > > > – I found this case thick part of the repeated, in other words

When I have 2 moves left and my current position is 1, I already know how many moves I have left.

③ How to define dp array?

Look again at this sentence:

When I have 2 moves left and my current position is 1, I already know how many moves I have left.

Two key factors are involved: the number of steps left and the current value, so a two-dimensional array is used

So dp[realstep][index] represents the number of subsequent moves left when the number of remaining steps is step and the position is index.

④ What is the change direction of the state and how is it changed

  • Think about the direction of change first

“When I have 2 moves left and my current position is 1, I already know how many moves I have left.”

What does this mean after this? What happens after this?

There will definitely be fewer and fewer steps, and the position will change according to the law. So the direction of change is to reduce the number of steps, and the position is to change according to the regulation.

So this fixed less and less of this “remaining steps,” is the core of the direction of change.

When we calculate, we can calculate the state of the small remaining steps first, and then calculate the large remaining steps.

  • How to change

Depending on the meaning and direction of the question, the number of remaining steps must be -1, and then there are 3 choices for the position (minus 1, unchanged, plus 1), so the method is the sum of the 3 choices.

dp[step][index] =dp[step-1][index-1] + dp[step-1][index] + dp[step-1][index+1]

⑤ What is the boundary state?

When the number of remaining steps is 0, only the current position is 0 is the final solution we want, set the value to 1 and provide it for later use, and consider all other positions with 0 steps as 0.

Dp [0] [0] = 1;

Dp [0] [index] = 0; (the index > 0)

implementation

So it finally comes out

  • Definition: dp{realstep][index]: how many moves are left when the remaining steps are step and the position is index.

  • Dp [step][index] = DP [step-1][index-1] +dp[step-1][index] +dp[step-1][index +1]

  • Boundary: dp[0][0] = 1;

Memory overflow processing

But this is a difficult question, so the above formula is set to a small difficulty:

The array length is very large, resulting in the maximum case dp[500][10^6] determines the timeout memory range if the index range is 0 to arrlen-1.

At this point, you have to think about whether index is unnecessary

Usually we can make our own little examples of this, for example

step=2, arr=10

Then see if it’s necessary to set index to 0 to 9 and take a few random steps

0-1 – > > 0

0-1 – > > 0

0 – > 0 – > 0

Huh? I found that there are only 3 cases, arR is so long after that no?

So I found a pattern:

The remaining steps must support him back to the origin!

In other words, the maximum range of index is at most step/2, no more, no more can go back.

So problem solved.

Practice on other similar topics

Leetcode-cn.com/problems/mi…

Click to follow, the first time to learn about Huawei cloud fresh technology ~