How to solve the problem of climbing stairs in leetcode
Editor to share with you how to solve the problem of climbing stairs in leetcode, I believe most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's learn about it!
Topic link
Https://leetcode-cn.com/problems/climbing-stairs/
Topic description
Suppose you are climbing the stairs. You need step n to get to the roof.
You can climb one or two steps at a time. How many different ways do you have to climb to the roof?
Note: given n is a positive integer.
Example 1:
Enter: 2
Output: 2
Explanation: there are two ways to climb to the roof.
1. Order 1 + 1
2. Order 2
Example 2:
Enter: 3
Output: 3
Explanation: there are three ways to climb to the roof.
1. 1 order + 1 order + 1 order
2. Order 1 + 2
3. Order 2 + 1
The first way of thinking of the solution to the problem
Tags: math
If we observe the mathematical law, we can see that this problem is Fibonacci series, then the formula of Fibonacci series can be used to solve the problem, the formula is as follows:
Time complexity: O (logn)
The first way of thinking code
Java version
Class Solution {
Public int climbStairs (int n) {
Double sqrt_5 = Math.sqrt (5)
Double fib_n = Math.pow ((1 + sqrt_5) / 2meme n + 1)-Math.pow ((1-sqrt_5) / 2meme n + 1)
Return (int) (fib_n / sqrt_5)
}
}
JavaScript version
/ * *
* @ param {number} n
* @ return {number}
, /
Var climbStairs = function (n) {
Const sqrt_5 = Math.sqrt (5)
Const fib_n = Math.pow ((1 + sqrt_5) / 2meme n + 1)-Math.pow ((1-sqrt_5) / 2meme n + 1)
Return Math.round (fib_n / sqrt_5)
}
The second way of thinking
Tags: dynamic plannin
In fact, the conventional solution of this problem can be divided into several sub-problems, and the number of methods for climbing the nth stairs is equal to the sum of two parts.
The number of ways to climb the first staircase of nmur1. Because if you climb one more step, you can get to the nth step.
The number of ways to climb the second staircase of nMel, because if you climb another 2 steps, you can reach the nth step.
So we get the formula DP [n] = DP [n-1] + DP [n-2]
Both dp [0] = 1 and dp [1] = 1 need to be initialized
Time complexity: O (n)
The second way of thinking code
Java version
Class Solution {
Public int climbStairs (int n) {
Int [] dp = new int [n + 1]
Dp [0] = 1
Dp [1] = 1
For (int I = 2; I
