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 order plus 1 order
2 order
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1 order plus 1 order plus 1 order
1 order plus 2 order
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 order
Input: 4
Output: 4
Explanation: There are five ways to climb to the top.
1 order plus 1 order plus 1 order plus 1 order
1 order plus 1 order plus 2 order
1 order plus 2 order plus 1 order
2 order plus 1 order plus 1 order
Two degrees plus two degrees
Input: 5
Output: 8
Explanation: There are eight ways to climb to the top of the building.
Order 1 + order 1 + order 1 + order 1 + order 1
1 order plus 1 order plus 1 order plus 2 order
1 order + 1 order + 2 order + 1 order
1 + 2 + 1 + 1
1 order plus 2 order plus 2 order
2 order plus 1 order plus 1 order plus 1 order
2 plus 1 plus 2
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