# LeetCode in Ruby: 70. Climbing Stairs

### Kaitian Xie twitter logo github logo Feb 26 '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 nth step from:

1. one step from `n-1`th step
2. two steps from `n-2`th 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)`

LeetCode in Ruby (11 Part Series)

DISCUSS
Classic DEV Post from May 13 '19

## What cool ideas have you seen for integrating new team members?

dev.to now has dark theme. 🌝

Go to the "misc" section of your settings and select night theme

P.S. You can also change font to sans serif, which a lot of folks prefer. 💖

P.P.S. It's also the best place to talk code amongst thoughtful developers, and it's totally open source  