70. Climb stairs

Link to force buckle topic: https://leetcode-cn.com/problems/climbing-stairs

Suppose you are climbing stairs. You need n steps to reach the roof.

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

Note: given n is a positive integer.

Example 1:

• Input: 2
• Output: 2
• Explanation: there are two ways to climb to the roof.
  • 1st order + 1st order
  • Second order

Example 2:

• Input: 3
• Output: 3
• Explanation: there are three ways to climb to the roof.
  • 1st order + 1st order + 1st order
  • 1st order + 2nd order
  • 2nd order + 1st order

thinking

If you haven't touched this topic, you will feel more difficult. Give more examples to find its law.

There is one way to climb to the first floor and two ways to climb to the second floor.

Then, the first floor stairs will take another two steps to the third floor, and the second floor stairs will take another step to the third floor.

Therefore, the state of the stairs to the third floor can be deduced from the state of the stairs to the second floor and the state of the stairs to the first floor, so we can think of dynamic programming.

Let's analyze the five parts of dynamic rules:

Define a one-dimensional array to record the status of different floors

1. Determine the meaning of dp array and subscript

dp[i]: there are dp[i] ways to climb the i-th stair

1. Determine recurrence formula

What if we can launch dp[i]?

From the definition of dp[i], we can see that dp[i] can be pushed in two directions.

First, dp[i - 1]. There are dp[i - 1] methods to go up the i-1 stairs, so it's dp[i] to jump one step at a time.

There are also dp[i - 2]. There are dp[i - 2] ways to go up the i-2 stairs. Then jumping two steps is dp[i].

Then dp[i] is the sum of dp[i - 1] and dp[i - 2]!

So dp[i] = dp[i - 1] + dp[i - 2].

When deriving dp[i], we must always think about the definition of dp[i], otherwise it is easy to deviate.

This shows the importance of determining the meaning of dp array and subscript!

1. How to initialize dp array

After reviewing the definition of dp[i]: there are methods in dp[i] to climb the i-th stair.

So I is 0 and dp[i] should be. There are many explanations for this, but they are basically explained directly to the answer.

For example, there is another way to forcibly comfort yourself to climb to the 0th floor, that is, do nothing, that is, dp[0] = 1, which is equivalent to standing directly on the roof.

But there's always something far fetched.

That's how to understand it: I think the way to go to the 0 th floor is 0. You can only go one step or two steps at a time. However, the floor is 0. If you stand directly on the roof, you don't need the method. dp[0] should be 0

In fact, this argument is meaningless. Most of the reasons why dp[0] should be 1 are because if dp[0]=1, i can traverse the problem from 2 in the recursive process, and then lean towards the result to explain that dp[0]=1.

From the point of view of dp array definition, dp[0] = 0 also makes sense.

It should be noted that the title says that n is a positive integer, and the title doesn't say that n is 0 at all.

Therefore, the initialization of dp[0] should not be discussed in this topic!

I believe that dp[1] = 1 and dp[2] = 2. There should be no dispute about this initialization.

Therefore, my principle is: if dp[0] is initialized, only initialize dp[1] = 1, dp[2] = 2, and then recurse from i = 3, so as to meet the definition of dp[i].

1. Determine traversal order

From the recursive formula dp[i] = dp[i - 1] + dp[i - 2]; It can be seen that the traversal order must be traversed from front to back

1. Example derivation dp array

For example, when n is 5, dp table (dp array) should be like this

70. Climb stairs

If there is something wrong with the code, print out the dp table to see if it is the same as what you deduced.

At this time, you should find that this is not the Fibonacci sequence!

The only difference is that there is no discussion about what dp[0] should be, because dp[0] is meaningless in this topic!

After the above five parts are analyzed, the C + + code is as follows:

// Version one
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n; // Because dp[2] is operated directly below to prevent null pointers
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) { // Note that i starts with 3
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

• Time complexity:

• Space complexity:

Of course, you can still optimize the space complexity. The code is as follows:

// Version 2
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n;
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};

• Time complexity:

• Space complexity:

Many dynamic gauge questions that will be explained later are actually the current state. Depending on the first two or the first three states, we can optimize the space, but I personally think it's enough to write a version in the interview. Ha, it's clear. If the interviewer requests to further optimize the space, we'll optimize it.

Because version 1 can reflect the ideological essence of dynamic rules and the change of recursive state.

expand

This topic can be further deepened, that is, step by step, two steps, three steps, up to m steps. How many methods can you climb to the n-step roof.

This is difficult again. In fact, this is a complete knapsack problem, but there is no such problem. Therefore, when I explain the knapsack problem later, today's problem will be told again from the perspective of knapsack problem.

Here I give my implementation code first:

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) { // Replace m with 2 and you can solve the problem of climbing stairs
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};

M in the code means that you can climb up to m steps.

The above code can't run. I mainly want to show that as long as I change m to 2 and paste it, I can solve the problem of AC climbing stairs. If you don't believe it, just stick it. Ha ha.

At this time, I found an excellent big factory interview question. The first question is to simply climb the stairs, and then look at the candidate's code implementation. If dp[0] is defined as 1, it can be difficult. Why dp[0] must be initialized to 1. At this time, the candidate may have to find various reasons why dp[0] should be 1. Then this is an inspection point. The definition of dp[i] is not deeply understood.

Then you can continue to challenge. If you step by step, two steps, three steps, until m steps, how many methods can you climb to the n-step roof. There is no original question on leetcode, which is definitely an excellent question to investigate the candidate's algorithm ability.

After this series of questions, the interviewer will know how the candidate's algorithm ability is.

In fact, the favorite question in the interview of large factories is this simple question, and then change slowly to investigate the candidates in small details.

summary

This topic and Dynamic programming: Fibonacci number The topic is basically the same, but you will find that this topic is compared with Dynamic programming: Fibonacci number It's much harder. Why?

The key is Dynamic programming: Fibonacci number The topic description has already given the recursive formula and how to initialize in the five parts of the dynamic gauge, and the remaining parts are naturally pushed out.

This topic needs to be analyzed one by one. You should feel it preliminarily now You should know this about dynamic programming! The five trilogy of motion rules given in.

Simple questions are used to master methodology. For example, yesterday's Fibonacci topic is simple enough, but yesterday and today can be analyzed by a set of methods. This is methodology!

So don't despise simple questions. It's not different from not mastering them. Only mastering the methodology and saying one, two or three can we learn by analogy and draw inferences from one instance!

On the sauce, learn the algorithm step by step and recognize the "code Capriccio"!

Other language versions

Java

class Solution {
    public int climbStairs(int n) {
        // Like the Fibonacci sequence
        if(n <= 2) return n;
        int a = 1, b = 2, sum = 0;

        for(int i = 3; i <= n; i++){
            sum = a + b;
            a = b;
            b = sum;
        }
        return b;
    }
}

// Conventional mode
public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
// Replacing arrays with variable records
public int climbStairs(int n) {
    int a = 0, b = 1, c = 0; // 1 time is required by default
    for (int i = 1; i <= n; i++) {
        c = a + b;          // f(i - 1) + f(n - 2)
        a = b;              // Record the value of the previous round
        b = c;              // Step backward 1 number
    }
    return c;
}

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        # dp[i] indicates the number of stairs climbing to the i-th stair, (1,2) (2,1) are two different types
        dp = [0] * (n + 1)
        dp[0] = 1
        for i in range(n+1):
            for j in range(1, 3):
                if i>=j:
                    dp[i] += dp[i-j]
        return dp[-1]

Go

func climbStairs(n int) int {
    if n==1{
        return 1
    }
    dp:=make([]int,n+1)
    dp[1]=1
    dp[2]=2
    for i:=3;i<=n;i++{
        dp[i]=dp[i-1]+dp[i-2]
    }
    return dp[n]
}

Javascript

var climbStairs = function(n) {
    // dp[i] is the i-th stair. How many ways can you climb to the roof
    // dp[i] = dp[i - 1] + dp[i - 2]
    let dp = [1 , 2]
    for(let i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n - 1]
};