# LeetCode in Ruby: 70. Climbing Stairs

### Kaitian Xie twitter logo github logo Mar 13 '19Updated on Dec 16, 2019・1 min read

LeetCode in Ruby (11 Part Series)

# 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 `n`th step from:

1. one step from `n-1`th step or,
2. two steps from `n-2`th steps.

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)`

Extra memory: `O(1)`

LeetCode in Ruby (11 Part Series)

DISCUSS Sore eyes?

dev.to now has dark mode.

Select night theme in the "misc" section of your settings ❤️

Classic DEV Post from Jun 14 '19

## FreeCodeCamp violated the rights of Medium authors  