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

This article is shared from Huawei Cloud Community “How did you think of dynamic planning?”, originally written by Breakdraw.

Usually practice algorithm problem learning algorithm knowledge, often found that the solution is written “dynamic programming”, which is a complex DP formula, in addition to the sound for new people

And the question is, how did he come up with this formula? Can I imagine? Does this work?

Add the fancy name “dynamic programming,” and dissuade a lot of people who try to understand it.

Dynamic programming sounds scary. Let’s put it another way

Internally, I prefer to call it “state caching” if you’re a service developer, I’m sure you’re familiar with the term, using caching to speed up the response time of repeated requests. The characteristic of this cache is that it is associated with other caches.

For example, our service needs to calculate the sum of some money within 7 days, and then cache it after calculation. And then we get a request to sum up the money for the 8 days so we just take the sum of the money for the 7 days we calculated before, and add the money for the 8 days.

The 1+4 way of thinking

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

  • Write a set of examples of the computation process along the timeout line
  • Based on the timeout example, what are the duplications and wastes?
  • How do I define the dp array
  • What is the direction of change of state and how is it changing
  • What is the boundary state

A simple example

Take a simple title:

Climb the stairs:https://leetcode-cn.com/probl…

This is the time to calm down and look at the example of the solution to see if there is a scenario of repeated experience, and this scenario of repeated experience is called the state. When I deal with dynamic programming problems, I always ask myself three questions, and I usually solve them successfully.

① Write a group of examples of the calculation process on the idea of timeout

So if we think about the easiest way to do it, we’re going to start at the beginning, and we’re going to take 1 step or 2 steps each time, and we’re going to see if we get to the end, and if we get to the end, we’re going to have plus 1. But this is going to be O (n^2), but I’m just going to do it this way, and I’m going to do it this way, 1->, 2- b>, 3- b>, 4->, 5, 1->, 2->, 3->, 5, 1->, 3->, 4->, 5, 1->, 3->, 5

② on the basis of the timeout example, what are the duplication and waste places?

On top, I found a repetition

So there are two ways to go from 3 to 5, and we’ve already calculated it after 1- BBB 0, 2, so when I go from 1 to 3 and then again, I don’t have to calculate it. In other words, by the time I get to 3, I already know how many moves I have left. Once you have found the duplication, you can start building the formula for dp.

How to define dp array?

Define the dp array, which defines the repetition mentioned above. And again, when I get to 3, I already know how many moves I have left. So dp[3] is how many ways you can go from three to three.

What is the change direction of the state and how does it change

  • Let’s think about the direction of change of state and look at this sentence again:

By the time I get to 3, I already know how many moves I have left

It means that it depends on the state that we’re going to be in so we’re going to calculate the state that we’re going to be in first, so we’re going to work backwards

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

And this is usually contained in the problem conditions, so depending on what they say, you either have to go 2 steps or you have to go 1 step, so every time I go to one level, the next time I can go to two different states. So for level 3, he has two moves, one move or two moves so he’s going to be dp[3] = dp[3+1] + dp{3+2} and if I set the number of levels to I, then this is dp[I] = dp[I +1] + dp[I +2]

⑤ What is the boundary state?

The boundary state is the state where you can get results without relying on the following states. In this case, it must be the last level dp[n], and the last level is one move by default. dp[n]=1

implementation

According to the above process, I have defined this state and change

  • Definition: dp[I] : represents the number of ways from the I level back
  • Dp [I] = dp[I +1] + dp[I +2];
  • Boundary: dp[n] = 1

It’s easy to write code like 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]; }

Advanced version, two dimensional dynamic programming

https://leetcode-cn.com/probl…

① Write a group of examples of the calculation process on the idea of timeout

The idea of timeout must be to simulate all walks like a search. Let’s say 1 steps=5 and arrlen=3. Simulate the position that keeps going. The number refers to the current location. 0 – > 1 – > 2 – > 1 – > – > 0 0 0 – > 1 – > 2 – > 1-1 – > > 0 0-1-1-1 – > > > > 1 – > 0 0-1-1-1 – > > > > 0 – > 0 0 – > 0-1-1-1 – > > > > 0…

② on the basis of the timeout example, what are the duplication and waste places?

0 – > 1 – > 2 – > 1 – > – > 0 0 0 – > 1 – > 2 – > 1-1 – > > 0 0-1-1-1 – > > > > 1 – > 0 0-1-1-1 – > > > > 0 – > 0 0 – > 0-1-1-1 – > > > > 0 0 – > 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 at this sentence again:

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

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

so

dprealstep

Represents the number of subsequent moves left when the number of steps remaining and the position is index.

What is the change direction of the state and how does it change

  • Consider 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’s going to happen after this? What’s going to happen after this?

Then there will be fewer and fewer steps, and the position will change according to the pattern. So the direction of change is that the number of steps is less, and the position is changed according to the rules.

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

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

  • How to change

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

dpstep = dpstep-1 + dpstep-1 + dpstep-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 supply it for later use. If the number of steps in other positions is 0, it is considered to be 0.

Dp0 = 1;

Dp0 = 0; (the index > 0)

implementation

So finally there it is

  • Dp {realstep][index]: When the number of remaining steps is step and the position is index, how many subsequent moves are left.
  • Direction and Variation: dpstep = dpstep-1 + dpstep-1 + dpstep-1
  • Boundary: dp0 = 1;

Memory overflow handling

But this one is a hard one, so it makes the above formula a little harder:

The size of the array is very large, so if we choose the index range from 0 to arrlen-1, then at most dp500 is bound to timeout the memory range.

So you have to think about whether it’s unnecessary to set the index that big

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

step=2, arr=10

And then see if it makes sense to set index between 0 and 9. Just walk around

0-1 – > > 0

0-1 – > > 0

0 – > 0 – > 0

Huh? I can see only 3 cases, the ARR is that long, okay?

Then I found the rule:

The remaining steps must carry him back to the beginning!

In other words, the maximum range of index is step/2 at most. You can’t go more than step/2.

So the problem is solved.

Other similar exercises

https://leetcode-cn.com/probl…

Click on the attention, the first time to understand Huawei cloud fresh technology ~