假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2

输出： 2

解释： 有两种方法可以爬到楼顶。

1.  1 阶 + 1 阶

2.  2 阶

示例 2：

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

1.  1 阶 + 1 阶 + 1 阶

2.  1 阶 + 2 阶

3.  2 阶 + 1 阶

---

思路

基本的动态规划问题，对于第n级台阶来说，有2种方法，1是到第n-1级，然后爬一个台阶；2是到第n-2个台阶，然后爬2个台阶，可以得出动态规划递推式：

$F(n) = F(n-1)+F(n-2)$

\(n=1\)的时候为1；\(n=2\)的时候为2

代码

class Solution(object):

    def climbStairs(self, n):

        """

        :type n: int

        :rtype: int

        """

        if n==1:

            return 1

        elif n==2:

            return 2

        else:

            tmp = [1,2]

            for i in range(2,n):

                tmp.append(tmp[i-1] + tmp[i-2])

            return tmp[-1]