DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 968,873 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Kaitian Xie
Kaitian Xie

Posted on • Updated on

LeetCode in Ruby: 70. Climbing Stairs

Dynamic Programming

def climb_stairs(n)
  p = 1
  q = 1

  (n - 1).times do
    temp = q
    q += p
    p = temp
  end

  q
end

This problem can be solved by using dynamic programming. We define f(n) as the number of ways you climb to the nth step from:

  1. one step from n-1th step
  2. two steps from n-2th step

Therefore, f(n) = f(n-1) + f(n-2), which is the same as the Fibonacci sequence. We have two bases cases: f(1) = 1 and f(2) = 2. The lines 4 and 5 are the first two numbers of the Fibonacci sequence. To get the nth number, we add up the numbers up to nth number. Here, we optimize the performance the just storing the previous two numbers.

Time complexity: O(n)

Space complexity: O(1)

Top comments (0)

🌚 Friends don't let friends browse without dark mode.

Sorry, it's true.