Preface explains

Algorithm learning, daily brush record.

Subject to connect

Climb the stairs

The subject content

Let’s say you’re climbing stairs and it takes you n steps to get to the top of the building.

How many different ways can you get to the top of a building when you can climb one or two steps at a time?

Note: given n is a positive integer.

Example 1:

Input: 2

Output: 2

Explanation: There are two ways to climb to the top.

  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.

  1. 1 order plus 1 order plus 1 order

  2. 1 order plus 2 order

  3. 2 order plus 1 order

The analysis process

Use the most intuitive induction method to find the answers to the first five items, and then compare them to find the rules.

Input: 1.

Output: 1.

Explanation: There is a way to climb to the top of the building.

  1. 1 order

Input: 4

Output: 4

Explanation: There are five ways to climb to the top.

  1. 1 order plus 1 order plus 1 order plus 1 order

  2. 1 order plus 1 order plus 2 order

  3. 1 order plus 2 order plus 1 order

  4. 2 order plus 1 order plus 1 order

  5. Two degrees plus two degrees

Input: 5

Output: 8

Explanation: There are eight ways to climb to the top of the building.

  1. Order 1 + order 1 + order 1 + order 1 + order 1

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

  3. 1 order + 1 order + 2 order + 1 order

  4. 1 + 2 + 1 + 1

  5. 1 order plus 2 order plus 2 order

  6. 2 order plus 1 order plus 1 order plus 1 order

  7. 2 plus 1 plus 2

  8. Order 2 plus order 2 plus order 1

With input 2 and 3 in the example, the first five results are as follows:

Input: 1, 2, 3, 4, 5

Output: 1, 2, 3, 5, 8

By comparing the results of input 1, 2, 3, 4 and 5, we can see that this is actually the Fibonacci sequence, f(n) = F (n-1) + f(n-2).

So the code looks like this:

Class Solution {public int climbStairs(int n) {return Fibonacci (n); } / / recursive method private static int the Fibonacci (int n) {if (n = = 1 | | n = = 2) {return n. } return Fibonacci (n-1) + Fibonacci (n-2); }}Copy the code

But the results are as follows:

Run the message timeout, when n = 45, run timeout.

Because recursion is time consuming, we can’t use recursion here.

We can choose to use the iterative method, one by one to work out the next result.

Each time, the last result is added to the current result. Each time, the last result is updated to the current result by 1 order, and the order is denoted as M.

If the order m is greater than or equal to the input order n, the loop ends and the current result is returned.

To solve the code

So the code for using the iterative method is as follows:

Class Solution {public int stairs (int n) {// F (n)=f(n-1)+f(n-2) // f(n)=f(n-1)+f(n-2) // f(n-2) =f(n-2); 1, 2, 3, 4, 5 // 1, 2, 3, 5, 8 // But if you use the recursive method, it will time out. When n=45, it will time out. Int currentTotal = 1; int currentTotal = 1; Int lastTotal = 1; int m = 1; While (m < n) {int temp = currentTotal; currentTotal += lastTotal; lastTotal = temp; ++m; } return currentTotal; }}Copy the code

Submit the results

It took 0ms to execute, beating 100.00% of users in time, 35.2MB of memory consumption, and beating 39.10% of users in space.

The original link

Take the stairs