问题描述

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Subscribe to see which companies asked this question

补充说明：

模拟上台阶，每次能上1级或者2级台阶，给定你一个台阶个数，问有多少种上台阶的方式。

方案分析

1. 这个问题一眼就让笔者回忆到上学和刚毕业找工作的那段日子了。这个问题像不像斐波那契数列？
2. 唯一与斐波那契数列不同的是n=1和n=2的时候。
3. 啥也不说了，上代码，不要用递归。

python实现

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==1:
            return 1
        if n==2:
            return 2
        prev = 2
        p_prev = 1
        result = 0
        for i in range(n-2):
            result = prev + p_prev
            p_prev = prev
            prev = result
        return result