Shulou(Shulou.com)06/01 Report--

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

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.