Leetcode: Climbing stairs
There is a given number of stairs n
. Stairs can be either taken two steps at a time or one step at a time. For a height of 1
, there is only one possible solution: 1
. For a height of 2
, there are two solutions: 1-1
or 2
.
The main trick in this task is to discover that this is a fibonacci-like sequence. Every next step depends on the steps before. Once this is discovered, the code is straightforward. First, cover the base cases, 1
and 2
. For the rest, append the sum of the first digits to a list and then pop the first element off the beginning. Finally, return the last digit.
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
l = [1, 2]
n -= 2
while n > 0:
l.append(l[0]+l[1])
l=l[1:]
n -= 1
return l[1]