70. Climb stairs | swipe questions and punch in

create by db on 2021-3-11 19:00:47

Recently revised in 2021-3-11 19:13:53

Idle time to have a tight mind, busy time to have leisure fun

70. Climb the stairs > contents

  • Topic describes
  • Thought analysis
  • AC code
  • conclusion

Topic describes

Returns the directory

Suppose you’re climbing stairs. It takes n steps to get to the top.

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

Note: given n is a positive integer.

Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top of the building. 1. Level 1 + Level 2. Level 2 Example 2: Input: 3 Output: 3 Description: There are three ways to climb to the top of the building. 1. 1 order + 1 order + 1 order 2. 1 order + 2 order 3Copy the code

Thought analysis

Does this sound familiar?

For example, how many ways can you jump up the NTH stair? Only n minus 1 and n minus 2 steps can be jumped up.

And so on, only (n-1) and (n-2) can jump up each stair, except for the first and second stairs.

fn(n) = fn(n-1) + fn(n-2)

Yes, that’s the Fibonacci sequence.

I can’t get Fibonacci to talk about flowers, but if you need to see this great problem

Idea 1: Recursion

When it comes to Fibonacci, the classic solution is recursion. But it runs out of time…

Idea 2: Scroll through an array

Here it goes:

AC code

recursive

/ * * *@param {number} n
 * @return {number}* /
var climbStairs = function (n) {
  if (n === 1) return 1
  if (n === 2) return 2
  return climbStairs(n - 1) + climbStairs(n - 2)}Copy the code

Solution 2: Scroll array

/ * * *@param {number} n
 * @return {number}* /
var climbStairs = function (n) {
  let p = 0,
    q = 0,
    r = 1
  for (let i = 1; i <= n; ++i) {
    p = q
    q = r
    r = p + q
  }
  return r
}
Copy the code

conclusion

Returns the directory

March hello, spring flowers. Come on!

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign

Postscript: Hello friends, if you think this article is good, remember to give a thumbs-up or star, your thumbs-up and star is my motivation to write more and richer articles!Making the address

Document agreement



dbThe document library 由 dbusingCreative Commons Attribution – Non-commercial Use – Same way Share 4.0 International LicenseGrant permission.

Based on thegithub.com/danygitgitOn the creation of works.

Use rights other than those authorized by this License agreement may be obtained fromCreativecommons.org/licenses/by…Obtained.