This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

Climb the stairs

Suppose you’re climbing stairs. It takes n steps to get to the top.

You can climb one or two steps at a time. How many different ways can you climb to the top?

Note: given n is a positive integer.

Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top of the building.

1. 1 order plus 1 order
2. 2 order

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top of the building.

1. 1 order plus 1 order plus 1 order
2. 1 order plus 2 order
3. 2 order plus 1 order

Second, train of thought analysis

• You’ve already swiped a lot of Leetcode before you know it. Today let’s take a look at an interesting leetcode– climbing stairs.
• It is normal for children to take up to two steps and at least one step. So let’s take that as the premise.
• Since it is a step, there is a starting point to the end of the problem, during the school often listen to the teacher said to be down-to-earth, seeking truth from facts. If we want to reach the end, we have to climb step by step.
• In other words, the end state is a step by step transition from the beginning state. And since it’s step by step it fits perfectly with our kinematic theory. So stair climbing is the test of dynamic programming

Transfer equation

• Dynamic programming why do I always start with the transition equation? Because he is the starting point of the movement. It’s the most important part. I’m not talking about the starting point here. Rather, it is a central part of the whole function of dynamic programming. It can’t go on without him.
• So let’s say that F of x is the number of steps we can take from the first step to the x step. From a certain step we can take one or two steps.

• We know from the figure above that F(x) can be a step from F(x-1) so it includes F(x-1); Or you could have F of x minus 2 coming in two steps. So we get the following equation

• And of course this is x starting at 1. So one might say, well, if x is equal to 1 then isn’t x minus 2 a negative number? Well, I should explain the transfer equation here. Press 0 when the node is in invalid state
• We can think of it this way, if the second piece is him and the previous piece is the first piece and he only has the first piece, then he can only be the first piece.

The initial value

• F (1) = 1. That shouldn’t be a problem. There’s only one way we can get to the first step. Now, the other thing we should notice is that F of 0, which is stateless, should be F of 0 =1.
• Let’s go backwards with F of 0. You can take two steps from the platform to the second step and that’s one way to do it. And F(2) contains F(0). So F(0)=1

From small to large

• Because F(1) = 1F(2) = F(1)+F(0) = 1+1 = 2. So there are two ways to get to the second step: one step on the first step plus two steps on the flat

AC code

The global saving

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

• The above is plain old dynamic programming, with extra arrays to store the result of each small problem to achieve a big result
• Submitting results to LeetCode is also objective

Local preservation

public int climbStairs(int n) {
    int prepre =1;
    int pre = 1;
    int current = 1;
    for (int i = 1; i < n; i++) {
        current = prepre + pre;
        prepre = pre;
        pre = current;
    }
    return current;
}
Copy the code

• Different from the global saving above, we only care about the state of the final n steps, so we do not need to save the state of the previous steps. There are only N steps, n-1 steps, n-2 steps that are relevant to us
• So we use three variables corresponding to the states of the three steps, n-2,N-1 and N. Of course, we just need to return the N step state

mathematical

• I don’t know if you have noticed that the formula of this problem is similar to the previous cracked translation. Before or if you think this formula is familiar to you
• Fibonacci seems to have this characteristic.1,1,2,3,5,8,13.... And we know that Fibonacci’s formula was also overridden.
• If we run the result directly from the formula, is it order one in time?

• Going from O(n) to O(1) is definitely an algorithmic optimization. After all, code is dead and people are alive. A lot of these so-called algorithms are actually pretty well summarized in mathematics. But the high-speed computing power of computers shielded his shortcomings. Therefore, mathematical formulas are often used in algorithms to solve problems quickly
• But at work we can’t say that the mathematical formula is better than our algorithm, because it’s possible to generate other operations in the formula. So we’re going to use both.

Four,

• Dynamic programming is really a good thing because it can simplify things that seem complicated.
• So there are three steps. Master it and you can eat all over the world like Cheng Chew gold

Welcome to like, follow and favorites